#递归算法

要想理解递归，请先理解递归 😀

大家应该听过这样的一个故事吧：

从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事
从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事
从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事

......

第一次听的时候大家都会笑， 这是什么故事呀，仔细想一想，其实这个故事有一个很特别的点：故事里包含了故事本身。

就像下面这张图，也有同样的特点，图里有一台电脑，电脑里也有一张完全一样的图，图中又有一台电脑 .....

编程中的递归就是用来解决有同样这类特点的问题的。

#什么是递归

递归（Recursion）是程序设计当中非常重要的一种思想，递归的本质是一种通过将问题分解为同类的子问题去解决问题的方法。 在编程中，递归是通过在函数中调用函数自身来实现的，递归函数也就是一个可以调用自己的函数。

下面通过一个简单的示例来看看什么是递归。

在讲解循环结构的时候，我们有过这样一个简单的练习，输入一个正整数 n，求 1 + 2 + ... + n 的和

当时我们是用下面这样的循环来完成的：

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
      sum = sum + i;
    }
    
    cout << sum << endl;
    return 0;
}

想一想，如果不用循环，怎么去实现呢？

假设我们已经实现了这样一个求和函数 sum()，输入参数 n ，可以得到从 1 加到 n 的和，大概长这样：

int sum(int n) {
  // 求和逻辑
  return 求和结果;
}

要求从 1 到 2，从 1 到 3，从 1 到 4 的和，可以直接调用函数 sum() 去得到：

sum(1) = 1
sum(2) = 2 + 1 = 2 + sum(1)
sum(3) = 3 + 2 + 1 = 3 + sum(2)
sum(4) = 4 + 3 + 2 + 1 = 4 + sum(3)

也就是说，求和可以表述成下面两种情况：

• 当 n = 1 时，sum(1) = 1
• 当 n > 1 时，sum(n) = n + sum(n - 1)

就像数学中的公式定义一样，我们可以直接用这两种情况去把 sum() 函数定义出来：

int sum(int n) {
  if (n == 1) return 1;
  else return n + sum(n - 1);
}

完整代码如下：

#include <iostream>
using namespace std;

// 用递归实现的累加求和函数
int sum(int n) {
  if (n == 1) return 1;
  else return n + sum(n - 1);
}

int main() {
  
    cout << sum(5) << endl;
    
    return 0;
}

以计算 sum(5) 为例，递归求解的过程如下图所示：

可以看到，利用递归思想去解决问题，通常分为下面这三步：

1. 第 1 步，找到问题与子问题之间的递推逻辑。 对于问题 N，找到规模更小的子问题 N-1，当 N - 1 解决了，N 也就解决了。对于本例来说就是 sum(n) = n + sum(n-1)。
2. 第 2 步，找到停递归调用停止的条件。 从N → N - 1 → N - 2 → ....，依次递推下去，终究会到达一个终点，也就是第 1 层最简单的问题（或者说已知的问题），这也是递归停止调用的条件，否则递归会无限调用下去。对于本例来说就是 sum(1) = 1。
3. 第 3 步，回归求解。 倒过来看，第 1 层解决了，那第 2 层也就解决了，第 2 层解决了，那第 3 层也就解决了，依次类推，进到第 N 层，也就是所求的问题也就解决了。

递推 + 回归，这也是递归这个名称的来源。

这里的第 3 步回归求解是由 C++ 内部的函数调用栈自动完成的，我们只需要关心第 1 步和第 2 步，也就是：

1. 找到问题与子问题之间的递推逻辑。
2. 找到递归调用的停止条件。

把前面的程序稍作改动，改动后代码如下：

#include <iostream>
using namespace std;

// 用递归实现的累加求和函数
int sum(int n) {
  printf("--- 函数 sum(%d) 正在调用 ---\n", n);
  if (n == 1) return 1;
  int rlt = sum(n - 1);
  printf("--- 函数 sum(%d)调用完成，返回上一层---\n", n - 1);
  return n + rlt;
}

int main() {

    cout << sum(5) << endl;

    return 0;
}

代码的作用是完全一致的，只是在每次递归调用 sum() 前后输出了一段信息，方便我们查看函数调用的顺序。

运行上面的程序，输出结果为：

可以看到，函数调用的顺序与我们上面那幅递归求解过程图是完全一致的。这正是因为函数调用栈的作用。

#函数调用栈

在程序运行时，每当你调用一个函数，计算机会把这个函数的信息（参数、返回地址、局部变量等）放入内存中的"栈"，称为调用栈（Call Stack）。函数执行完毕后，这个函数的信息会从栈中弹出，回到上一个函数的执行位置。这个"栈"是由 C++ 在内部自动维护的，并不需要我们手动做任何工作。

栈的特点是"先入后出（LIFO，Last In First Out）"，先调用的最后弹出，最后调用的最先弹出。

为了帮助大家理解函数调用栈，可以尝试从非递归的角度再来看一看。

#include <bits/stdc++.h>
using namespace std;

int sum1(int n) {
  printf("--- 函数 sum1 正在调用 ---\n");
  return n; // 相当直接返回 1
}

int sum2(int n) {
  printf("--- 函数 sum2 正在调用 ---\n");
  int r = n + sum1(n - 1);
  printf("--- 函数 sum1 调用完成，返回上一层 ---\n");
  return r;
}

int sum3(int n) {
  printf("--- 函数 sum3 正在调用 ---\n");
  int r = n + sum2(n - 1);
  printf("--- 函数 sum2 调用完成，返回上一层 ---\n");
  return r;
}
int main() {
  cout << sum3(3) << endl;
  return 0;
}

运行程序，输出结果为：

我们用非递归的方式实现了同样的功能，不过这并不实用，如果我们要求 sum(100) 难道我们要写 100 个这样的函数？

用递归实现刚好就解决了这样的问题，你可以把每次 sum(n-1) 的调用看作是对一个完全不同的函数的调用，只是这个函数刚好同名，并且有同样的实现逻辑，这也正是一个问题如果可以用递归去实现需要满足的条件之一。

希望通过递归求解过程图、函数调用栈讲解以及非递归实现模拟这三种方式，大家对递归有一个更清晰的认识和理解。

#示例：斐波那契数列

斐波那契数列（Fibonacci），一直是一个介绍递归应用的经典例子。

斐波那契数以递归的方法来定义，其数学表达如下所示：

$\begin{cases} & F_0=0 \\ & F_1=1 \\ & F_n=F_{n-1} + F_{n-2}\end{cases}$

用文字来描述，就是斐波那契数列是由 0 和 1 开始，之后的斐波那契数是由之前的两数相加而得。

从第 1 项开始，前面的几个斐波那契数是：

1、1、2、3、5、8、13、21 ......

需要注意的是，0 是第零项，而不是第一项

题目描述：

输入一个大于等于 3 的正整数 n，求斐波那契数列第 n 项

输入输出样例：

输入：

输出：

分析求解：

根据斐波那契数列的定义，很容易得出递归求解的三步，写出的递归函数 fib() 如下：

int fib(int n) {
  if (n == 0 || n == 1) return n;
  else return fib(n - 1) + fib(n - 2);
}

完整的实现代码：

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
  if (n == 0 || n == 1) return n;
  else return fib(n - 1) + fib(n - 2);
}

int main() {
  int n;
  cin >> n;  
  
  cout << fib(n) << endl;  
  
  return 0;
}

#示例：求阶乘

在数学中，阶乘（Factorial）的定义是：

$n! = 1 \times 2 \times 3 \times … \times n$

$n$ 的阶乘用 $n!$ 表示。根据定义，我们可以直接用一个普通的循环去实现求阶乘，代码如下：

#include <bits/stdc++.h>
using namespace std;

int factorial(int n) {
  int rlt = 1;
  for (int i = 1; i <= n; i++) {
    rlt *= i;
  }
  return rlt;
}

int main() {
  int n;
  cin >> n;

  cout << factorial(n) << endl; 
 
  return 0;
}

如果我们用数学的方式来重新表达 $n!$，你会发现它本身就是递归的：

$n!=n\times (n-1)$

我们已经得到递归求解的第 1 个条件：问题与子问题之间的递推关系，也就是说，要计算 $n!$，只需要计算 $(n-1)!$，然后再乘以 $n$ 就可以了。

也很容易知道 $1! = 1$ 这个阶乘的初始条件，也是递归调用的停止条件。

用递归实现的代码如下：

#include <iostream>
using namespace std;

int factorail(int n) {
  if (n == 0 || n == 1) return 1;
  else return n * factorail(n - 1);
}

int main() {
    int n;
    cin >> n;
    
    cout << factorail(n) << endl;
    
    return 0;
}

输入

输出

特别的，这里考虑了 $0! = 1$ ，从数学上的定义来说，这才是阶乘的初始条件，从逻辑上更加完备。

#示例：汉诺塔问题

汉诺塔问题（Hanoi Problem）是源于法国数学家爱德华.卢卡斯编写的一个关于印度的古老传说。

相传河内某间寺院有三根银棒，一根银棒上从下往上按照大小顺序摞了 64 片黄金圆盘。寺院里的僧侣依照一个古老的预言，以下述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。

移动规则：

1. 每次只能移动一个圆盘。
2. 大盘不能叠在小盘上面。

现在小朋友都可以买到下面这种汉诺塔的益智玩具

求解汉诺塔问题也是递归应用的一个非常经典的示例。

如下图所示，假设在 A 柱上共有 5 个圆盘，目标是按汉诺塔的移动规则，将 A 柱上的圆盘全部移到 C 柱上去。（假设圆盘从上到下编号依次为 1、2、3、4、5）

要解决 5 个（N）圆盘的问题，先解决 4 个（N - 1）圆盘的问题，把前 4 个（N - 1）圆盘看作一个整体，这样我们可以运用前面讲到的递归思想去解决，可以分为下面三个步骤。

第 1 步： 将 N - 1 看作一个整体后，先把这个整体移到 B 柱。

第2步： 再把 A 柱上的一个圆盘移到 C 柱。

第3步： 再把 B 柱上的 N- 1 个圆盘整体移到 C 柱。

依次类推下去，最终变成解决 2 个圆盘的问题，直到解决 1 个圆盘的问题。

实际上，要将 $n$ 个圆盘，按照规则从 A 柱移动到 C 柱，总共需要移动 $2^n - 1$ 次，想一想为什么呢？

最终完整的实现代码

#include <iostream>
using namespace std;

void hanoi(int n, char source, char temp, char target) {
  if (n == 1) {
      cout << source << " → " << target << endl;
  } else {
    	// 
      hanoi(n - 1, source, target, temp); // A → B
      hanoi(1, source, temp, target); // A → C
      hanoi(n - 1, temp, source, target); // B → C
  }
}

int main() {
    int n;
    cin >> n; // A 柱上盘子的数量
    
    hanoi(n, 'A', 'B', 'C');
    
    return 0;
}

输入1：

输出1：

输入2:

输出3:

这里的函数参数作个说明：

// n 是圆盘的数量
// 从 a 移动到 b，b 柱是用于中间临时存放的柱子
void hanoi(int n, char source, char temp, char target)

#示例：猜数字游戏

不知道大家还记得不？在循环章节，我们讲到过一个猜数字的游戏，当时是让计算机帮我们随机生成一个 1 ～ 100 的数字，我们通过不断输入去猜，直到猜正确！

现在我们反过来，我们自己想一个 1 ～ 100 的数字，让计算机通过算法去猜，直到猜对！

计算的猜的算法是，每一次取可猜的数字范围的中间数，这样每猜一次，将范围缩小一半，整体下来效率最高。实际上，这正是以后我们会讲到的二分查找（折半查找）算法。

完整的实现代码：

#include <iostream>
using namespace std;

int guess(int low, int high) {
  int mid = (low + high) / 2;
  
  cout << "我猜的数是：" << mid << ", ";
  cout << "我猜大了还是小的呢？通过以下编号选择" << endl;
  cout << "1. 猜大了" << endl;
  cout << "2. 猜小了" << endl;
  cout << "3. 相等" << endl;
  
  char res;
  cin >> res;
  
  if (res == '3') {
     cout << "哈哈，我猜对喽！" << endl;
  } else if (res == '1') {
      guess(low, mid - 1);
  } else {
      guess(mid + 1, high);
  }
}

int main() {
  cout << "你可以想一个 1 ~ 100 之间的整数，让我来猜吧！" << endl;
  
  guess(1, 100);
  
  return 0;
}

下面是一个测试结果，假如我心里想的数字是 65 ，下面是计算来猜的过程：

#练习：数列求和-递归

#题目描述

有一数列如下： $1, 2, 4, 7, 11, 16, 22 ……$ ，试求该数列前 $n$ 项之和。

#输入描述

一个整数 $n$ （ $0 \lt n \lt 10000$ ）

#输出描述

包含一行，为一个整数，表示数列求和的结果

#输入输出样例

输入数据

输出数据

#代码实现

• 3zj7k5nub - C++ - OneCompiler

#include <iostream>
#include <iomanip>
using namespace std;
//计算第n项
int series_sum(int n){
	if ( n==1 ) {
		return 1;
	}else {
		return (n-1) + series_sum(n-1);
	}
}

int main() {
	int n,rlt=0;
	cin>>n;
	
	for (int i = 1; i<=n; i++) {
		rlt = rlt + series_sum(i);
	}
	
	cout<<rlt<<endl;
}

#拓展思考

上面的代码实现是用递归实现的，当然，这个任务可以不用递归去完成。可以通过普通的循环或者递推去完成，下面把用普通循环的方法及递推的方法都附上，便于参考。对于一个任务，善于多从不同的角度去多思考，多种方法求解，思考哪方法在哪种场景下更适合。

#递推求解（数组）

注意这里的 sum = 1，这是因为我们累加求和时 i 是从第 2 项开始计算的， 因此默认先把第 1 项算上了。

#include <iostream>
using namespace std;

const int N = 1010;
int q[N];

int main() {
  int n, sum = 1; 
  cin >> n;
  
  q[1] = 1;
  
  for (int i = 2; i <= n; i++) {
    q[i] = (i - 1) + q[i - 1];
    sum = sum + q[i];
  }
  
  cout << sum << endl;
  
  return 0;
}

#递推求解（不用数组）

• 3zjfax9mn - C++ - OneCompiler

实际上，我们也可以不用数组来实现递推求解，因为最终我们需要得到的是前 N 项的和，中间的所有数都是临时的，通过第 i 项，我们可以推出 i+1 项，这里我们用 x 和 y 来交替推进，循环中的每一轮，x 和 y 都是不同的。

#include <iostream>
using namespace std;

int main() {
  int n, y, sum = 1;
  cin >> n;
  
  int x = 1;
  
  for (int i = 2; i <= n; i++) {
    y = x + i - 1;
    sum = sum + y;
    x = y;
  }
  
  cout << sum << endl;
  return 0;
}

#练习：次方求解

#题目描述

给定一个数 $n$，求它的 $m$ 次方

#输入输出样例

输入数据 1：

输出数据 1:

输入数据 2:

输出数据 2:

#题目分析

这里需要注意，$n^m$ ，这里幂 $m$ 可能是正数，也可以是负数，而正数与负数次方的计算方式是不一样的！

• 当 m > 0 时，$n^m = n \times n^{m-1}$
• 当 m < 0 时，$n^m = \frac{1}{n^{-m}}$

#完整的实现代码

#include <iostream>
using namespace std;

// 这里只考虑整数次方
float pow(float n, int m) {
  if (m == 0) {
    return 1;
  } else if (m < 0) {
    return 1.0 / pow(n, abs(m));
  } else {
    return n * pow(n, m - 1);
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  
  cout << pow(n, m) << endl;
  
  return 0;
}

#练习：求解最大公约数

我们在函数章节也讲了用普通的循环来求解最大公约数的方法，这里我们需要使用递归去完成。

#题目描述

给定两个正整数，求它们的最大公约数。

#输入描述

输入一行，包含两个正整数 $(< 1,000,000,000)$。

#输出描述

输出一个正整数，即这两个正整数的最大公约数。

#输入输出样例

输入数据1

输出数据2

#题目解析

最大公约数（Greatest Common Divisor，简称 GCD），又称最大公因数或最大公因子，是指几个自然数公共的因数中最大的一个。

例如：30 和 18 的公约数有 1、2、3、6，其中最大的是 6，因此 6 是 30 和 18 的最大公约数。

我们通常使用 辗转相除法（又称欧几里得算法） 来求最大公约数。辗转相除法基于如下原理：两个数的最大公约数等于其中较小的数和两数相除的余数的最大公约数。

仍然以求 30 和 18 的最大公约数为例。

• 30 % 18 = 12
• 18 % 12 = 6
• 12 % 6 = 0 （余数为 0，停止计算，最大公约数为 6）

#实现代码

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
  if(!b) {
      return a;
  }
  return gcd(b, a % b);
}

int main() {
    int a, b;
    cin >> a >> b;
    
    cout << gcd(a, b) << endl;
    
    return 0;
}

#练习：求最小公倍数

在数学，最小公倍数与最大公约数有下面的换算关系。

$lcm(a, b) = \frac{a \times b}{gcd(a, b)}$

上面我们已经通过辗转相除法求出了最大公约数，最小公倍数就可以直接利用上面的公式来完成。

#实现代码

#include <bits/stdc++.h>
using namespace std;

// 求最大公约数
int gcd(int a, int b) {
  if(!b) {
      return a;
  }
  return gcd(b, a % b);
}

// 直接利用最大公约数求最小公倍数
int lcm(int a, int b) {
  return a * b / gcd(a, b); 
}

int main() {
    int a, b;
    cin >> a >> b;

    cout << lcm(a, b) << endl;

    return 0;
}

在 C++17 中，有内置的 gcd 与 lcm 函数可以直接使用。

#include <numeric>
std::gcd(a, b);
std::lcm(a, b);

#对比递推与递归

我们在上一章学习了递推算法，一些简单的问题，既可以用递推去实现，也可以用递归去实现。但两者的实现方式是完全不同的。

递推是通过从已知的初始值出发，逐步推导出后续的值，通常使用循环结构来实现。递推是一个从已知到未知的过程。

递归是通过将问题分解为更小的子问题，然后重复调用函数来解决问题。每次递归调用会根据一个特定的条件来缩小问题的规模，直到遇到基准情况，实际上是一个从未知到已知，再回到未知的过程。

递推和递归各有优劣，需要根据具体问题选择合适的方式。

通常来说，递推的代码更直观，也没有额外的栈空间开销，对于简单的迭代问题，用递推去实现更加简单明了；递归调用会占用额外的栈空间，如果递归调用层次太深，容易导致栈溢出，但对于一些本身具有递归性质的问题（如树/图的遍历、分治算法等），递归能更自然地表达和解决问题。

#小结

递归就是通过在函数中调用自身来解决一些重复的问题，它的优点是简洁、直观，在解决一些复杂的问题时非常有效，然而递归算法也需要谨慎使用，因为它可能会导致额外的函数调用开销，带来潜在的性能问题。

我们在后面的很多算法里都会用到递归，因此 理解和掌握递归的思想是非常重要的。