递归基础与递归算法

一、概念

递归函数即自调用函数，在函数内部直接的或者间接地调用自己。递归采用了分治的思想，在解决问题时，我们需要将整体分割成部分，从最小的基本部分入手，逐一解决。其中部分通常和整体具有相同的结构，这样部分可以继续分割，直到最后分割成不可再分割的基本部分。递归函数必须定义一个终止条件，即什么情况下终止递归，终止继续调用自己，如果没有终止条件，那么函数将一直调用自己，直到程序栈耗尽，这时候等于是写了一个Bug!

如求阶乘函数：

int fac(int n)
{
	if (n < =1)
		return 1;
    return n * factorial(n - 1);

}

求解问题 f(6)，由于 f(6) = n * f(5)，所以 f(6) 需要拆解成 f(5) 子问题进行求解，同理 f(5) = n * f(4)，也需要进一步拆分，...，直到 f(1)，这是「递」，由于f(1) 是可以直接知道答案的，所以 f(1) 可以直接解决掉，而导致 f(2) = 2 f(1) = 2 也解决了，...，以此类推 f(n) 到最后也解决了，这是「归」，所以递归的本质是能把问题拆分成具有相同解决思路的子问题。直到最后被拆解的子问题再也不能拆分，解决了最小粒度可求解的子问题后，在「归」的过程中自然顺其自然地解决了最开始的问题。

总结递归的特点：

1. 使用递归时，一定要有明确的终止条件！

2. 递归算法解题通常代码比较简洁，但不是很容易读懂。

3. 递归的调用需要建立大量的函数的副本，尤其是函数的参数，每一层递归调用时参数都是单独的占据内存空间，他们的地址是不同的，因此递归会消耗大量的时间和内存。而非递归函数虽然效率高，但相对比较难编程。

4. 递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。

二、递归与循环的区别

递归适合从大往小推，而循环适合从小往大推，而递归难以实现从小往大，但是循环却可以实现从大往小；递归就是把整个计算的路直接走完了，然后根据递归基走回去一遍把坑填了；循环就是不知道自己走多远的路，直到限制条件出现挡住了。简单来说递归就是从计算的终点走到起点再走到终点，循环就是从起点走到终点，或从终点走到起点。

三、递归算法通用解决思路

我们在上一节仔细剖析了什么是递归，可以发现递归有以下两个特点：

1. 一个问题可以分解成具有相同解决思路的子问题，子子问题等，换句话说这些问题都能调用同一个函数。

2. 经过层层分解的子问题最后一定是有一个不能再分解的固定值的（即终止条件），如果没有的话,就无穷无尽地分解子问题了，问题显然是无解的。所以解递归题的关键在于我们首先需要根据以上递归的两个特点判断题目是否可以用递归来解。

经过判断可以用递归后，接下来我们就来看看用递归解题的基本套路（四步曲）：

1. 先定义一个函数，明确这个函数的功能。如何明确？我们一定是只考虑函数当前层的逻辑内容，只需弄清楚这一层循环中我们的输入输出是什么。由于递归的特点是问题和子问题都会调用函数自身，所以这个函数的功能一旦确定了， 之后只要找寻问题与子问题的递归关系即可。

2. 接下来寻找问题与子问题间的关系（即递推公式），这样由于问题与子问题具有相同解决思路，只要子问题调用步骤 1 定义好的函数，问题即可解决。所谓的关系最好能用一个公式表示出来，比如 f(n) = n * f(n-1) 这样，如果暂时无法得出明确的公式，用伪代码表示也是可以的，发现递推关系后，要寻找最终不可再分解的子问题的解，即（临界条件），确保子问题不会无限分解下去。由于第一步我们已经定义了这个函数的功能，所以当问题拆分成子问题时，子问题可以调用步骤 1 定义的函数，符合递归的条件（函数里调用自身）。

3. 第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中。

4. 最后也是很关键的一步，根据问题与子问题的关系，推导出时间复杂度，如果发现递归时间复杂度不可接受，则需转换思路对其进行改造，看下是否有更靠谱的解法。

四、递归的基本类型

1. 线性递归：单向的递归，一条路走到死；

2. 多向递归：在递归的过程中可能出现多种不同的方向，但是最终也只能选择一个方向，属于线性递归的一种；

3. 多路递归：具体就是递归分成了 f(n) + f(n-1) 之类的不同道路，其每一个子递归都可能再做多次递归（通常都是一分为二，故也称二分递归）。这种递归方式可以直接用多叉树结构来理解，递归基就是叶节点；

4. 尾递归：递归调用在递归实例中恰好是最后一步操作，这种递归都能易于变为迭代版本。

五、递归基本类型简单描述

1) 在递的过程中解决问题

function recursion(大规模)
{
	if(end_condition)  //1.明确的停止条件
		end;    //2.在停止时所执行的解决方案
	else
	{
		solve;   //3.在递的过程中，即划分问题前的解决方案
		recursion(小规模); //4.缩小运行规模
	}
}```

### 2) 在归的过程中解决问题

```cpp
function recursion(大规模)
{
	if(end_condition)  //1.明确的停止条件
		end;    //2.在停止时所执行的解决方案	
	else
	{
		recursion(小规模); //3.缩小运行规模
		solve;   //4.在归的过程中，即划分问题后的解决方案
	}
}

3) 多路递归时（如二叉树的迭代遍历），对于不同的路来说，解决方案可处于递或者归的位置

function recursion(大规模)
{
	if(end_condition)  //1.明确的停止条件
		end;    //2.在停止时所执行的解决方案
	else
	{
		recursion1(小规模); //3.缩小运行规模，子规模1
		solve;    //4.对于不同的子递归，其所处的位置不同
		recursion2(小规模); //5.缩小运行规模，子规模2
	}
}

4) 尾递归

特例，solve的位置总是飘忽不定，可能在递过程或归过程，也可能在停止解决方案中，也可能不出现，所以其不是必须的。

六、经典代表例子

1）阶乘实现（线性递归问题/尾递归问题）

#include <iostream>
using namespace std;

//阶乘的递归实现是一种线性递归，solve过程是在递的过程中（在归时才进行结果计算）

long long factorial1(long long n)
{
	if (n == 1)
		return 1;

	return n*factorial1(n - 1);
}

int main()
{
	cout << "阶乘递归：" << factorial1(10) << endl;

	return 0;
}

2）Fibonacci数（多路递归问题/线性递归问题/尾递归问题）

#include <iostream>
using namespace std;

//最经典无脑的斐波拉切实现，属于二分递归，将原递归策略不断地进行二分处理

long long Fibonacci1(long long n)
{
	if (n == 1 || n == 2)
		return 1;

	return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}

int main()
{

	long long n = 30;
	cout << "经典斐波拉切实现：" << Fibonacci1(n) << endl;

	return 0;
}

3）杨辉三角形取值（多路递归问题/尾递归问题）

对于杨辉三角形，我的理解是以第一行和第一列开始算，即x与y的初始值都应该是1，所以代码中相关数值的选取也是按照此思想来的。

#include <iostream>
using namespace std;

//杨辉三角形的特征就是，一个数等于两肩数之和

long PascalsTriangle(int x, int y)
{
	//1.首先判断数据的输入正确
	if( x > 0 && y > 0)
	{
		//2.然后判断递归基，取三角形的边均为1
		if (x == y || x == 1)
			return 1;
	
		//3.如果都可以则执行二分递归，按照两肩的位置进行递归（属于在归时完成结果计算）
		return PascalsTriangle(x - 1, y - 1) + PascalsTriangle(x - 1, y);
	}
	
	return -1;
}

int main()
{
	cout << "杨辉三角形的(3,5)位置为：" << PascalsTriangle(3, 5) << endl;

	return 0;
}

七、递归优化——记忆化

以斐波那契数列数列为例，当我们计算第6项的时候，不难发现里面有些项我们在反复计算，有的项要计算很多次。这对计算机的内存和运行时间都是极大的浪费。既然是在反复计算，那么在第一次计算的时候，我们完全可以把结果记录下来，在接下来的计算当中可以直接调用该结果，这样可以减少计算机的内存与运行时间，提高程序执行的效率。

#include<bits/stdc++.h>
using namespace std;
long long n,a[85];
long long work(long long x)
{
	if(x==1) return 1;
	
	if(x==2) return 2;
	
	if(a[x]>0) return a[x];
	
	a[x]=work(x-1)+work(x-2);
	
	return a[x];
}

int main()
{
	cin>>n;

	cout<<work(n);

	return 0;
}