递归、迭代、动态规划的区别与联系

一、定义

递归：程序调用自身,从顶部将问题分解，通过解决掉所有分解出来的小问题，来解决整个问题。
迭代：利用变量的原值推算出变量的一个新值。递归中一定有迭代，但是迭代中不一定有递归。
动态规划：通常与递归相反，其从底部开始解决问题。将所有小问题解决掉，进而解决的整个问题。

下面通过斐波那契数列相关代码来比较一下三者。
斐波那契数列：1，1，2，3，5，8，11，13…

二、递归

自上而下调用函数本身，速度较慢，不推荐。

要知道第n个数，必须要先知道第n-1和第n-2个数。
而想要知道第n-1个数必须要先知道第n-2和第n-3个数，
想要知道第n-2个数必须要先知道第n-3和第n-4个数。

f(n)
=f(n-1)+f(n-2)
=f(n-2)+f(n-3)+f(n-3)+f(n-4)
=…

int fibonacci(int n)
{
	if (n <= 2)
		return 1;
	else
		return fibonacci(n - 1) + fibonacci(n - 2);
}

三、迭代

利用原值去求解下一个值，一般比递归更加快速。

由第一个数和第二个数去求解第三个数，
由第二个数和第三个数去求解第四个数，
以此类推。

f(3)=f(2)+f(1)
f(4)=f(3)+f(2)
f(5)=f(4)+f(3)
…

int fibonacci(int n)
{
	if (n <= 2)
		return 1;
		
	int first = 1, second = 1, answer;
	for (int i = 3; i <= n; i++)
	{
		answer = first + second;
		first = second;
		second = answer;
	}
	
	return answer;
}

四、动态规划

动态规划甚至比迭代还要更快一点，但是采用了空间换时间。

1、级问题的最优解包含了其子问题的最优解，也就是最优子结构性质。
2、有些子问题的可能需要多次计算，即子问题的重叠的性质。
3、子问题的解存储在一张表格里，这样每个子问题只用计算一次。
4、需要额外的空间以节省时间。

int fibonacci(int n)
{
	vector <int> dp;
	dp.push_back(0);
	dp.push_back(1);
 
	for (int i = 3; i <= n; i++)
		dp.push_back(dp[i-1] + dp[i-2]);
 
	return dp[n];
}