递归与递推

递归

递归的定义：函数的自我调用
例：

• 利用递归实现阶乘

#include<bits/stdc++.h>
using namespace std;
int out(int n)
{
	int res;
	if (n == 1)
	{
		res = 1;
	}
	else
	{
		res = out(n-1)*n; //在这里又调用了一次out,即out(n-1) = out(n-2)*(n-1)
	}
	return res;
}
 
int main()
{
	cout << out(5);
	return 0;
}

• 基于递归的算法
  • 深度优先搜索 DFS

学递归有感而发：

• 只有上帝和出题人知道递归传参究竟是怎么传的

---

• 递归的缺陷
  使用递归计算斐波那契数列数列第n项(n < 50)

int f(int n)
{
	int res;
	if (n == 1 || n == 2)
	{
		res = 1;
	}
	else
	{
		res = f(n-1)+f(n-2);
	}
	
	return res;
}
 
int main()
{
	for (size_t i = 1; i <= 50; i++)
	{
		cout << i <<"	"<<f(i) <<endl;
	}
	
	return 0;
}

• 运行不难发现，在第46项以后，运行极为缓慢
• 由此引入 递推