常见算法-递归

你为什么学不会递归

递归

分治

分治法将原问题划分成若干个规模较小而结构与原问题相同或相似地子问题,然后分别解决这些子问题,最后合并子问题地解,即可得到原问题地解。

具体分为以下三个步骤:

  • 分解:将原问题分解为若干和原问题拥有相同或相似结构地子问题。
  • 解决:递归求解所有子问题。如果存在子问题地规模小到可以直接解决,就直接解决它。
  • 合并:将子问题的解合并为原问题的解。

前提:分治法分解出的子问题应当是相互独立、没有交叉的。

递归

递归就在于反复调用自身函数,但是每次把问题范围缩小,直到范围缩小到可以直接得到边界数据的结果,然后再在返回的路上求出对应的解。

递归的逻辑中一般有两个概念:1 递归边界 2 递归式(或递归调用)。递归式是将原问题分解成若干个子问题的手段,而递归边界则是分解的尽头。而且我们解决问题的前提就是找到递归边界和递归式。用递归式将问题规模不断缩小,用递归边界作为不断向下递归的终点。在得到最小问题的解的时候,在一步步返回来进行稍大问题规模的求解,直至结束。

递归三大要素

  1. 明确你这个函数想要做什么
  2. 寻找递归结束条件
  3. 找出函数的等价关系式

使用递归求解n的阶乘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int hh(int n){
if(n==0) return 1; //这里应该是等于0,而不是1 事情要考虑全面
else return n * hh(n-1);
}
int main()
{
int n;
cin>>n;
int num = hh(n);
cout << num << endl;
return 0;
}

求Fibonacci数列的第n项。

斐波那契数列是满足F(0) = 1,f(1) = 1,F(n) = F(n-1) + F(n-2) (n≥2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

using namespace std;

int Fibonacci(int n){
if(n==0) return 1;
else if(n==1) return 1; //因为n==1的时候不允许再有n-2的时候了,所以这个也应当算作边界
else return Fibonacci(n-1) + Fibonacci(n-2);
}
int main()
{
int n;
cin>>n;
int num = Fibonacci(n);
cout << num << endl;
return 0;
}

总结:要实现一个递归函数,那么就要有两样东西:递归边界递归式。其中递归边界用来返回最底层的结果,递归式用来减少数据规模并向下一层递归。

全排列(Full Permutation)

一般把1~n这n个整数按某个顺序摆放的结果称为这n个整数的一个排列,而全排列指这n个整数能形成的所有排列。从递归的角度,如果把问题描述成“输入1~n这n个整数的全排列”,那么它就可以被分为若干个子问题:“输出以1开头的全排列” “输出以2开头的全排列”···“输出以n开头的全排列”。 下面以n=3为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
using namespace std;
int n;
const int maxn = 5;
int p[maxn]; //用来存放当前的排列
int hashTable[maxn] = {false}; //hashTable[x]为整数x已经在数组p中时为true
void generateP(int index){
if(index == n+1){ //递归边界
for(int i=1;i<=n;i++){
printf("%d",p[i]);
}
printf("\n");
return;
}
for(int x = 1;x<=n; x++){ //枚举1~n,试图将x填入p[index]
if(hashTable[x] == false){
p[index] = x;
hashTable[x] = true;
generateP(index + 1);
hashTable[x] = false;
}
}
}
int main()
{
n = 3;
generateP(1);
return 0;
}

n皇后问题

Q:n皇后问题是在一个n*n的国际象棋棋盘上放置n个皇后,使得这n个皇后两两均不在同一行,同一列,同一条对角线上,求合法的方案数。

思路: 因为每一行只能够放置一个皇后,每一列也只能够放置一个皇后,那么如果把n列皇后所在的行号依次写出,那么就会是一个1~n的一个排列。于是可以在上面全排列的基础上进行求解。由于当到达递归边界时表示产生了一个全排列,所以需要在其内部判断是否为合法方案,即遍历每两个皇后,判断它们是否在头一条对角线上,若不是(即符合要求),则累计计数变量即可。以上思路已经可以解决问题,该方法我们称之为暴力法。若想要再进行优化,我们就会发现,当已经放置了一部分皇后之后,可能剩余的皇后无论怎样放置都不可能合法,此时就没有必要再向下递归了,直接返回上层即可,这样可以减少很多的计算量。演示代码入下:

1
//未完待续......
您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------