递归算法

递归

本文将简单介绍递归算法及其应用

一个故事

​

简介

递归是一种思想。
递归是一种思维方式。
递归是一种算法。

递归算法的实现

递归算法，通常是借助于递归函数来实现的。
一个函数直接或间接调用自己——递归函数

一个简单的例子

计算n的阶乘：n!
n!=12…*(n-1)*n
规定0!=1
（数据范围0<=n<=20）
样例输入：5
样例输出：120

分析

代码实现

#define LL long long
LL f(int n)
{
	if(n==0)return 1;
	return n*f(n-1);
       // return !n ? 1 : n*f(n-1);
}
int main()
{
	int n;
	cin>>n;
	cout<<f(n)<<endl; 
	return 0;
}

斐波那契数列的递归实现

练习

输入x和n的值，求x^n。
样例输入：2 3
样例输出：8

请写出求x^n的递归函数

分析

递归的优缺点

解决效率低的方法：

1、记忆化
2、转递推

小结：

递归过程必须解决两个问题

跳进递归——递归计算的公式
跳出递归——递归结束的条件

递归过程的算法描述框架：

if (到达递归出口)
返回递归出口处的函数值;
else
递归计算公式并返回结果;

结束语

递归有两个过程：
1、把大问题一步一步往小问题分解；
2、从最小的问题开始，根据递推关系一步一步得到新的解决方案，最后得到所得解。
所以，递归的本质其实还是递推关系，没有这个递推关系，就无法产生递归定义的合理性，合理性就是要求能够调用函数的本身，函数可以永远适用，这里面的思想就是使用一种相同的方法来描绘整个世界。只不过，递归还想强调一种分治的思想，这种思想在解决复杂问题中有非常重要的应用。