算法笔记-递归

递归是一种神奇的算法，代码总体上比较简单，思路也很好理解。在解题层面，我们只用关心递归的全局，而不必去关心递归的详细执行过程。当你做到这一点之后，递归这种算法就会非常的清晰了。

1、初识递归：

递归：是一种自己调用自己的算法，它会在函数的实现中直接或者间接的调用它本身

为了更好的认识递归，这里有个故事：

从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢：

......

读完这个故事，你会发现这不就是套娃吗，一直无限重复。

其实递归就是这样一种算法，会一直重复的执行某种逻辑，这个逻辑我们用函数来实现

那么递归要和上面的故事一样，一直无限重复下去吗？这样代码不就成了死循环吗(~~TLE警告~~)

// 递归函数，要执行的逻辑就是讲一个故事
void fun(){
    cout<<"从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢："<<endl;
    
    fun(); // 自己调用自己，实现递归(套娃)
}

所以在做题时，我们还会引入一个限制条件，来限制递归的运行，这个条件也叫做递归边界

也就是说，当递归执行到了边界之后，就直接结束，就不会产生死循环了

// 新增一个参数：要重复执行的次数
void fun(int n){
    // 当次数为0，说明故事讲完了
    if(n == 0) return;
    // 讲一次故事，讲一次少一次
    cout<<"从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢："<<endl;
    // 上面讲了一次故事，所以后面还要讲 n-1 次
    fun(n-1); 
}

有了递归函数之后，我们在主函数里面正常调用即可。

2、举一反三：

(1) 用递归实现sum(n)来求1~n的全部整数之和

现在我们假设这个问题很难 (~~其实就是小学二年级水平~~)

现在我们要想知道 sum(n) 的结果，但是 sum(n) 太难算了，我们可不可以拆成更小的问题来求解呢？

算不出来，我们拆成：

......

~~算不出来~~，最后

经过以上的流程，问题1：sum(n)的定义是什么？问题2：sum(n)是怎么递归的？问题3：sum(n)的递归边界是什么？

// sum(n)的定义，返回1~n的全部整数之和
int sum(int n){
	// 递归边界：n = 1时，sum(1) = 1
	if(n == 1) return 1;
	// 递归求和：sum(n) = sum(n-1) + n
	return sum(n-1) + n;
}

从解题思路到代码实现，我们没有思考任何和计算有关的问题，也没有去管递归的细节是怎么实现的。只从问题本身来思考递归

码上练习：求1~n的和

码上练习：求阶乘

(2) 角谷猜想传送门

读完题可知：n是奇数就把这个数*3+1，n是偶数就把这个数除以2，一直重复这个过程。从递归的角度看，应该如何解题呢？

先定义一个函数，表示把n变为1所需要的运算次数。

当 n 为奇数时：，意思就是从的过程，变成了从的过程，中间运算了一次。

当 n 为偶数时：，意思就是从的过程，变成了从的过程，中间也运算了一次。

递归边界就是：n = 1时结束

// f(n)的定义，把n变成1所要运算的次数
int f(int n){
	// 当n = 1时，递归结束
	if(n == 1) return 0;
	// n为偶数时，f(n) = f(n/2) + 1
	if(n%2==0) return f(n/2)+1;
	// n为奇数时，f(n) = f(n*3+1) + 1
	else return f(n*3+1)+1;
}

(3) 求斐波那契数列传送门

读完题，我们用可以用来表示斐波那契的第n项，于是：

其实到这里，你会发现我们剩下只用思考递归边界，在此之前还是刚刚的三个问题。

问题1：f(n)的定义是什么？问题2：f(n)是怎么递归的？问题3：f(n)的递归边界是什么？

问题1和2都非常的明显了，那递归边界呢？由题可知，斐波那契数列从开始，按照思路递归回去

每执行一次，就会递归两次，所以边界也应该有两个

// f(n)的定义，求斐波那契的第n项
int f(int n){
	// 当n==1或者n==2时都要结束
	if(n == 1 || n == 2) return 1;
	// 递归执行的逻辑：f(n) = f(n-1)+f(n-2)
	return f(n-1) + f(n-2);
}

我们依然没有直接计算，全都交给电脑计算，我们也不用思考递归如何详细执行的

码上练习：爬楼梯、上台阶、斐波那契、分糖果等类型的题目由于递归次数较多，会产生大量的重复计算，所以要采用记忆化递归的方法。不然就会TLE

3、渐入佳境

递归调用的本质就是一棵树，一个函数里面递归几次，就是一颗几叉数

用斐波那契数列来举例，一个函数里面递归了两次，那么这就是一棵二叉树。我们可以用树的形式把递归调用的过程画出来，然后你会发现有大量重复的计算。

最直观的例子，刚刚写的递归求斐波那契数列的函数，当n=100时，程序就G了

那么怎么解决呢，既然会有重复计算，那我们可不可以把每次计算的结果保存下来，下次遇到相同的计算就直接从历史结果中获取呢

要实现这个思路，我们可以定义一个历史结果的数组，每当要计算时，我们就可以从历史结果中找，找到了就直接返回，不用计算；没有找到就递归计算，再把计算完的结果放到历史结果数组里面

// 历史结果数组，存放每次计算完后的值
int his[20005];
// f(n)的定义，求斐波那契的第n项
int f(int n){
	// 当n==1或者n==2时都要结束
	if(n == 1 || n == 2) return 1;
	// 在递归计算之前，先判断历史结果里面是否计算果
	// 找到记录不为零，说明f(n)计算过
	if(his[n] != 0) return his[n];
	// 否则就直接计算结果，并保存到历史数组中
	return his[n] = f(n-1) + f(n-2);
}