[数据结构与算法] 递归

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 递归 -> 正文阅读

[数据结构与算法]递归

递归是一种不断调用自身函数的一个过程，就像是套娃一样，一层套着一层，很多人初学时都会被绕晕，但其实只要抓住递归的两个重要概念—递归边界和递归式，学起来就会轻松许多，下面我们由浅入深来讲讲递归。

一、n!

首先从最简单的例子 $n!$ 讲起， $n!$ 可以用一个循环来解决，为了让大家更好理解递归，我们用递归来实现 $n!$ ， $n!$ 的计算是 $n\times(n-1)\times\cdots\times1$ , 它写成递推式是 $n\times(n-1)!$ ，这样就把规模为 $n$ 的问题转化为规模为 $n ? 1$ 的问题了，如果 $F (n)$ 是 $n!$ 的话，那么递归式就是 $F(n)=F(n-1)\times n$ 了，如果 $n$ 的规模一直缩小，最终会到 $F (0)$ ，即 $0! = 1$ ，这样我们就可以将 $F (0) = 1$ 作为递归边界，那么用递归实现 $n!$ 的整体思路就是在函数 $F (n)$ 里面调用 $F (n ? 1)$ ，直到 $F (0)$ ，然后再一层一层返回答案，用代码实现如下(以 $3!$ 为例)

#include <cstdio>
using namespace std;

int F(int n){
	if(n == 0) return 1; //递归边界 
	return n*F(n-1); //递归式 
} 

int main(){
	printf("%d", F(3));
	return 0;
}

我们简单讲一下代码，首先主函数调用函数 $F (3)$ ，判断 $n\neq0$ ，执行下一条语句，返回 $3\times F(2)$ ，由于 $F (2) 是未知的$ ，这时就会继续调用 $F (2)$ ，以此类推，直到 $1\times F(0)$ ，此时达到递归边界 $n = 0$ ，条件成立，返回 $F (0) = 1$ ，然后返回 $F(1)=1\times F(0)=1$ ，依次向上返回结果，用一个恒等式表示就是 $F(3)=3\times F(2)=3\times2\times F(1)=3\times 2\times 1\times F(0)=3\times 2\times 1\times 1$ 正向就是函数的调用过程，逆向就是结果的返回过程。

二、Fibonacci数列的第n项

第二个经典的例子就是Fibonacci数列的第 $n$ 项，Fibonacci是指0,1,1,2,3,5,8 $\cdots$ 这样的自然数列，他的递推定义式是 $F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N^*）$ 从定义中我们可以看出递归边界是 $F (0) = 0 ， F (1) = 1$ ，递归式是 $F (n) = F (n ? 1) + F (n ? 2)$ ，根据上面 $n!$ 我们可以写出代码

#include <cstdio>
using namespace std;

int F(int n){
	if(n == 0) return 0; //递归边界 
	if(n == 1) return 1; //递归边界
	return F(n-1)+F(n-2); //递归式 
} 

int main(){
	printf("%d", F(3));
	return 0;
}

用恒等式来表示就是 $F (3) = F (2) + F (1) = (1 + 0) + F (1) = 1 + 1$ 当然用递归实现Fibonacci数列会伴随者大量重复的计算，比如计算完 $F (4)$ 时，会计算 $F (3)$ ,而 $F (3)$ 本身也要再计算一次，我们可以用数组把已经计算好的用数组记录下来，这样可以避免很多重复计算，动态规划可以更好解决这个问题。

递归通用模板

通过以上两个例子，我们可以总结出递归的模板，如下

int fuction(所需参数){
	-----------------
	|    递归边界    |
	-----------------
	|     递归式     |
	-----------------
}

通过上面两个递归的总结，我们只需要找出所需参数、递归边界和递归式就可以了，而所需参数往往与递归边界有着密切关联，一般是作为条件或者满足条件后执行代码用到的参数。

三、Hanoi

一根柱子称原柱上，套有n个盘子，依次从小到大地从上往下地排序着，需要将这n个盘子移动一个目标柱上，要求在移的过程中，大的盘子不可以在小的盘子上面。可以使用一根辅助柱子;

这题的递归边界显然就是当只有一个盘子的时候，直接从原柱移动到目标柱，接下去就是寻找递归式了，当有n个盘子时，需要将n-1个盘子移动到临时柱，然后将原柱的盘子移动到目标柱，最后将临时柱的n-1个盘子移动到目标柱，而想将n-1个盘子移动到目标柱，就要重复以上步骤，所以递归式有三个步骤：

把n-1个盘从源柱移动到临时柱上；
把原柱上剩余的1个盘移动到目标柱上；
把临时柱上的n-1个盘移到目标柱上。

根据上述可知所需参数就是一个整型来记录盘子的个数，还有三个字符型来记录三根柱子的移动

#include <cstdio>
using namespace std;

void Hanoi(int n, char a, char b, char c){
	//递归边界 
	if(n == 1){
		printf("%c-->%c\n",a,c);
		return;
	}
	Hanoi(n-1,a,c,b);//将n-1个盘子从A柱(原柱)移动到B柱(临时柱) 
	printf("%c-->%c\n",a,c);//A柱(原柱)只剩下最后一个盘子,直接移动到C柱(目标柱) 
	Hanoi(n-1,b,a,c);//将B柱(临时柱)上的盘子移动到C柱(目标柱) 
}
int main(){
	Hanoi(3,'A','B','C');
	return 0;
}

四、全排列问题

将1~n进行排列，一共有几种排列？

这个排列组合的问题我们高中就学过了，其中一种方法就是填充法，从n个数选一个出来填充在第一个位置，然后从剩下的数中再选一个出来填充在第二位，以此类推，直至将数全部填充完，那如果用代码呢，那就要用到循环了，从1开始依次填充数字，直至所有数字都填充完毕，用index表示当前填充的位数，那么递归边界就是当index等于n+1的时候。那递归式呢，我们用一个数组来存放填充的数，那我们怎么知道这个数是否已经填充过了呢，这时候就需要有一个数组来记录这个数是否已经填充过了。然后在填充过程中判断这个数是否已经被填充了，有就跳过，没有就填充，然后填充下一位，直到所有的数都被填充完，所需的参数就是下标index。代码如下：

#include <cstdio>
using namespace std;

const int maxn = 20;
int n, p[maxn], hashTable[maxn] = {};

void Permutation(int index){
	//递归边界 
	if(index == n+1){
		for(int i = 1; i <= n; i++){
			printf("%d", p[i]);
		}
		printf("\n");
		return;
	}
	//递推式，有就跳过，没有就填充，然后填充下一位
	for(int i = 1; i <= n; i++){
		if(!hashTable[i]){
			p[index] = i;
			hashTable[i] = 1;
			Permutation(index+1);
			hashTable[i] = 0;
		}
	}
}

int main(){
	n = 3;
	Permutation(1); //从1开始填充
	return 0;
}

五、八皇后

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

这一题与全排列的思想是一样的，可以使用二维的数组来记录皇后是否放置，这样我们枚举的时候就需要 $C_{n^2}^n$ ，仅仅八皇后就需要4426165368次了，根据题目任意两个皇后都不能处于同一行、同一列，也就是说一行只能放一个皇后，我们不妨用数组的下标表示皇后所在的行数，数组内容表示皇后所在的列数，然后用一个数组记录这一列是否放置了皇后，与上题类似，递归的边界就是index等于n+1，递归式也是一样的，唯一的差别就是同一斜线不能放置两个皇后，所以现在我们只需要解决皇后不在同一斜线上就可以了。
$\begin{array}{r|r|r|r|r|}\hline 4&&&&\\ \hline 3&&&&0\\ \hline 2&0&&0&\\ \hline 1&&*&&\\ \hline &1&2&3&4\\ \end{array}$
我们在(1,2)放了一个皇后*，那么0的位置就不能放皇后了，观察*和0，我们可以发现两个所在行坐标相减会等于所在的列坐标相减，我们找出这个条件就可以开始写代码了。

#include <cstdio>
#include <cmath>
using namespace std;

int hashTable[10] = {}, queen[10], count = 0;

void EightQueen(int index){
	//递归边界，n=8
	if(index == 9){
		//打印棋盘
		for(int i = 1; i <= 8; i++){
			for(int j = 1; j <= 8; j++){
				if(queen[i] == j) printf("1 ");
				else printf("0 ");
			}
			printf("\n");
		}
		printf("\n");
		count++;
		return;
	}
	//递归式
	for(int i = 1; i <= 8; i++){
		//遍历以放置的皇后，判断要放置的皇后与之前的皇后是否在同一斜线上
		int flag = 1;
		for(int j = 1; j < index; j++){
			if(abs(queen[j]-i) == index-j){
				flag = 0;
			}
		}
		if(!hashTable[i] && flag){
			queen[index] = i;
			hashTable[i] = 1;
			EightQueen(index+1);
			hashTable[i] = 0;
		}
	}
}

int main(){
	EightQueen(1);
	printf("%d", count);
	return 0;
}