程式設計微知識 (五) 遞迴(Recursion)和迭代(Iteration)

2016-01-20

14808
0
微知識

遞迴(Recursion):一種透過重複將問題分解為同類的子問題而解決問題的方法。在大部分的程式語言中都支援函數的自我呼叫，也就是說在程式語言中可以通過呼叫函數本身來進行遞迴。

迭代(Iteration):其目的通常是為了接近所需求的目標或結果。每一次對過程的重複被稱為一次"迭代"，每一次迭代得到的結果通常會被用來作為下一次迭代的初始值。

本文以C++實作執行。

遞迴:在程式設計中要執行遞回的話基本上是屬於函式的堆疊呼叫。思考模式往往是找出問題的規律，然後透過此規律來重複使用相同的方法來縮減問題的範圍，直到找出我們所需要的部分。

範例:Fibonacci

完整程式碼如下:

#include <iostream>
using namespace std;

int fib(int n);

int main() {

	cout << "fib(0) = " << fib(0) << endl;
	cout << "fib(1) = " << fib(1) << endl;
	cout << "fib(2) = " << fib(2) << endl;
	cout << "fib(3) = " << fib(3) << endl;
	cout << "fib(4) = " << fib(4) << endl;
	cout << "fib(5) = " << fib(5) << endl;
	cout << "fib(6) = " << fib(6) << endl;	

	system("pause");
	return 0;
}


int fib(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1)
		return 1;
	else
		return (fib(n - 1) + fib(n - 2));
}

執行結果如下:

迭代:在程式設計中要執行迭代的話，通常都是使用迴圈來實作。迭代是透過一個已知的初始值開始反覆運算，到最後求出答案的一個過程。

範例:Fibonacci

#include <iostream>
using namespace std;

int fib(int n);

int main() {

	cout << "fib(0) = " << fib(0) << endl;
	cout << "fib(1) = " << fib(1) << endl;
	cout << "fib(2) = " << fib(2) << endl;
	cout << "fib(3) = " << fib(3) << endl;
	cout << "fib(4) = " << fib(4) << endl;
	cout << "fib(5) = " << fib(5) << endl;
	cout << "fib(6) = " << fib(6) << endl;


	system("pause");
	return 0;
}

int fib(int n)
{
	int n1 = 0;
	int n2 = 1;
	int result = n;
	for (int i = 2; i <= n; i++)
	{
		result = n1 + n2;
		n1 = n2;
		n2 = result;
	}
	return result;

}

執行結果如下:

有夢最美築夢踏實

活在當下認真過每一天

我是阿夢也是Ace

微知識

回首頁