注：本文默认对递归有一定了解，所以刚开始会cover一些简单的例子

一、何为递归⌗

何为递归？程序反复调用自身即是递归。

用数学代入法来理解就好。

假设我们用递归来算阶乘 f(n) $$f(n) = n * f(n-1)$$ f 里面用到了 f， 怎么理解呢？

很简单，把式子展开即可：

f(6)
=> 6 * f(5)
=> 6 * (5 * f(4))
=> 6 * (5 * (4 * f(3)))
=> 6 * (5 * (4 * (3 * f(2))))
=> 6 * (5 * (4 * (3 * (2 * f(1)))))
=> 6 * (5 * (4 * (3 * (2 * 1))))
=> 6 * (5 * (4 * (3 * 2)))
=> 6 * (5 * (4 * 6))
=> 6 * (5 * 24)
=> 6 * 120
=> 720

看到递归了吗？

先递进，再回归——这就是「递归」。^[对于递归有没有什么好的理解方法？ - 方应杭]

二、递归的重要组成部分⌗

明白了什么是递归之后，我们就要从一个抽象的层面上来对他抽丝剥茧，究竟什么构成了一个递归？

首先，要继续接下面的内容，我们需要引入一个概念——栈帧（stack frame）。我们可以把栈帧简单理解成一层层的盒子，每当我们调用一次函数，关于该函数的调用以及返回地址就会被放到栈帧的顶上。拿阶乘举例，我们最后画出来的栈帧就是这样的：

Stack Frame

我们可以看到在栈帧的顶上是$f(1)$，到这个时候我们就没有去计算所谓的$f(0)$了。这是因为我们现在到了一个递归的终止条件。顾名思义，当到这个地方时阶乘就不会继续往下，因为没有了意义。

第二步，我们要明白每一层要给上一层提供什么信息。继续看阶乘的算法，我们可以发现，每一层都会返回一个$n * f(n-1)$。其中这个就是我们留下来的信息，而这个信息就会被逐步返回，直到返回第一层。这也叫做 recursive case。也就是没有到终止条件时，递归会做什么。

总的来说，有两个条件在递归中非常重要：

  • 递归的终止条件
  • 没有到终止条件时做的事情

三、递归的例子⌗

接下来我们看一下如何真正的实现一个递归：

阶乘⌗

首先，阶乘是递归的一个经典问题，因为我们已经发现了阶乘的递推的公式 $$f(n) = n * f(n-1)$$

所以我们很快就可以写出如下代码：

int factorial(int n){
    if(n == 0){
        return 1;
    }
    return n * factorial(n - 1);
}

简单分析一下，我们的递归结束条件就是 $n == 0$，因为在这里我们没有继续再调用自己往下算了。

接着，我们也实现了我们在递归时要做的东西，即$n * f(n - 1)$。可以想象一下，没有这一部分，我们是没有办法能够把这个阶乘问题划分成更小的子问题的。所以这一部分是必须有的。

所以，一个非常重要的点就是，你要确保你的函数在每次递归之后，都能够解决一点原来的问题。这也叫做问题的分解，这也是递归的精髓所在——将原问题不断拆分为与原问题等价的小问题。

斐波那契数列⌗

斐波那契数列的是这样一个数列 ：1、1、2、3、5、8、13、21、34….， 即第一项 f(1) = 1, 第二项 f(2) = 1….., 第 n 项目为 f(n) = f(n-1) + f(n-2)。 求第 n 项的值是多少。

首先，我们拿到一个问题时，我们要确认递归的终止条件是什么，在这里我们可以发现，终止条件就是 $f(1) = 1$。因为到了这里之后，我们都不需要继续往下算了。但是我们同样也要处理 $n == 2$ 的情况，因为根据我们的递推公式，如果不处理 $n == 2$的情况，如果输入2，很明显我们调用一个 f(0)。但是f(0)在斐波那契数列是不存在的，所以我们要特殊的处理这一部分。

所以我们可以先写出如下代码：

int f(int n){
    if(n == 1){
        return 1;
    }else if(n == 2){
        return 1;
    }
    //TODO: Fill this part
}

接着，我们需要知道什么是我们的递归要做的事情。我们可以发现，斐波那契数列也有一个很良心的递推公式，也就是 $f(n) = f(n-1) + f(n-2)$。每一项会等于该项的前两项之和。

所以我们可以把上面的代码完善成这个：

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

这样我们就可以计算任何位置n的斐波那契数列。

回文⌗

上面我们举了两个数字的例子，但是递归能处理的不仅仅是数字。它还可以解决字符串的问题【当然不仅仅是字符串】。

我们把一个字符串称之为回文，如果它有如下特性：该字符串正着读和反着读都是同一个字符串。比如，racecar，正着读和反着读都是 racecar。

要解决这个问题，我们首先要明白什么是 “该字符串正着读和反着读都是同一个字符串”。我们可以看到，为什么 racecar 会是回文字符串，因为它的第一个字符与最后一个字符相同，第二个字符与倒数第二个字符相同……。所以，这就是回文的意义。

接着，我们要明白什么是我们的递归终止条件，这里我们先分类讨论一下：

① 针对奇数个字符的字符串

奇数个字符的字符串有个特点，就是我们有一个字符会不用比较。拿 racecar 举个例子： r == r a == a c == c

但是，我们可以发现，我们不需要比较 e == e ，因为只有一个字符了，我们不需要比较。所以这就是奇数个字符的终止条件。

② 针对偶数个字符的字符串

但是针对偶数个字符的回文字符串，我们会把所有的字符都比较了，这也就意味着，我们不会有奇数个字符的字符串的那种“只剩中间一个字符”的情况。所以，针对偶数个字符的字符串，终止条件就是字符长度为0.

弄明白了结束条件，我们就要看什么是递归条件。

其实我们前面也已经分析过了，我们需要比较第一个字符是否与最后一个字符相同，第二个字符与倒数第二个字符相同……这就是我们的递归要解决的问题。所以我们可以得到如下的代码：

bool isPalindrome(string s){
    if(s.length() == 1 || s == ""){
        return true;
    }
    return s[0] == s[s.length() - 1] && isPalindrome(s.substr(1, s.length() - 2));
}

这个函数可能乍一看比较难理解，但实际上就是我们首先比较了第一个字符是否与最后一个字符相同，接着我们从原来的字符提取了子字符串（去掉首尾各一个字符的字符串），然后把这个字符串作为参数再次调用了函数。

比如，racecar提取子字符串，就会变成 aceca；然后，第二轮再被提取子字符串，变成 cec……

至于为什么要用 && 来连接两个表达式：这是因为，我们要的是保证第一个字符与最后一个字符的同时，还要保证子字符串也是回文字符串，如果有任何一个地方出问题，那么整个字符串就肯定不是回文字符串。

汉诺塔⌗

最后，我们来解决一个递归里比较复杂的问题，汉诺塔。这也是一个稍微偏向图形化的问题：

汉诺塔问题：古代有一个梵塔，塔内有三个座 A、B、C，A 座上有 64 个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这个盘子从 A 座移到 B 座，但每次只能允许移动一个盘子，并且在移动过程中 ，3 个座上的盘子始终保持大盘在下，小盘在上。

汉诺塔 - 2个

汉诺塔 - 3个

① 如果只有 1 个盘子，则不需要利用 B 塔，直接将盘子从 A 移动到 C 。 ② 如果有 2 个盘子，可以先将盘子 2 上的盘子 1 移动到 B ；将盘子 2 移动到 C ；将盘子 1 移动到 C 。这说明了：可以借助 B 将 2 个盘子从 A 移动到 C ，当然，也可以借助 C 将 2 个盘子从 A 移动到 B 。 ③ 如果有 3 个盘子，那么根据 2 个盘子的结论，可以借助 C 将盘子 3 上的两个盘子从 A 移动到 B ；将盘子 3 从 A 移动到 C ，A 变成空座；借助 A 座，将 B 上的两个盘子移动到 C 。 ④ 以此类推，上述的思路可以一直扩展到 n 个盘子的情况，将将较小的 n-1 个盘子看做一个整体，也就是我们要求的子问题，以借助 B 塔为例，可以借助空塔 B 将盘子 A 上面的 n-1 个盘子从 A 移动到 B ；将 A 最大的盘子移动到 C ， A 变成空塔；借助空塔 A ，将 B 塔上的 n-2 个盘子移动到 A， 将 C 最大的盘子移动到 C， B 变成空塔。^[对于递归有没有什么好的理解方法？ - 程序员吴师兄]

所以，我们可以写出如下代码：

void moveTower(int n, char start, char finish, char tmp){
    if(n == 1){
        moveSingleDisk(start, finish);
    }
    moveTower(n - 1, start, tmp, finish); //借助finish柱子，把n-1个移动到tmp上
    moveSingleDisk(start, finish); //把最底下的那个移动到finish上
    moveTower(n - 1, tmp, finish, start); //借助start柱子，把n-1个移动到finish上
}

四、怎么理解递归⌗

可能到回文字符串问题，或者是汉诺塔问题的时候，递归就变得有些难以理解了。一个最经常的问题就是，我怎么能够确保我的递归过程是对的？这常常会给初学递归的人一种烧脑的感觉，因为他们往往不够相信自己。

这里我们就要引入一个新的概念 —— Recursive leap of faith。

翻译成中文就是 递归信念的飞跃，简单来说就是相信你的递归会在每一层操作正确，而你自己只需要去关心，结束条件是否正确，我是否执行了正确的递归操作。

比如针对汉诺塔，我们不需要在纸上写每一层是怎么样的，每一次栈帧是怎么样的。我们只要明白：

  • 当只剩一个的时候，我会把它从开始柱子移动到结束柱子
  • 在有多个的时候，我会把 n - 1 个移动到临时的柱子上，然后把第 n 个移动到结束的柱子上，最后再把临时柱子上的 n - 1 个移动到结束的柱子上

可以看到，这么思考我们根本不需要关注细节，我们关注的只是抽象的步骤，以及递归的退出条件。这就已经足够了。

五、递归回溯⌗

对于许多现实世界的问题，解决过程由一系列决策点组成，在这些决策点上，每个选择都会引导您沿着某个路径走得更远。

如果做出了正确的选择，最终程序就会得到解决方案。另一方面，如果你走到了死胡同，或者发现自己在某个地方做出了错误的选择，你就必须回到以前的决策点，尝试另一条不同的道路。使用这种方法的算法称为回溯算法。^[Programming Abstractions in C++ - Eric S. Roberts]

这就是回溯——我们需要尝试所有的可能的“路径”，然后输出或者返回需要的内容。

传统的递归与递归回溯的对比如下：

传统递归与递归回溯的对比

下面我们来看一下递归回溯的例子。

六、递归回溯的例子⌗

子集⌗

首先最经典的一个模型就是子集。

问题：给一个集合，输出它的所有子集。

比如$S = {1, 2, 3}$，它的子集就是： $$ \emptyset \ {1}\ {2}\ {3}\ {1, 2}\ {1, 3}\ {2, 3}\ {1, 2, 3}\ $$

问题就是我们怎么写一个程序来探索这些所有的可能性呢？

其实我们可以把这个问题转换一下，生成子集，实际上就是问你要不要保留某个元素。我们拿${1, 2}$的子集举一个例子，如图所示：

{1,2}的子集

我们可以看到，子集实际上就是对每个位置的元素，你选择排除还是不排除。所以根据这个思路，我们可以继续思考这个问题。

首先，我们要确认退出条件。在不考虑优化的情况下，退出条件当然就是当集合没有元素可供你选择的时候，也就是空集的时候。

其次我们确定递归要干的事情——调用两次递归函数，一次结果包含某个元素，一次不包含这个元素

所以我们可以写出如下代码：

void subsetHelper(Set<string> s, Set<string> result){
    if(s.size() == 0){
        cout << result << endl;
    }
    string element = s.front(); //返回第一个元素;

    subsetHelper(s - element, result + element); // s - element 会返回一个不包含element的集合; result + element 会返回一个加入了 element 的集合
    subsetHelper(s - element, result); //不包含element
}
void subSet(Set<string> s){
    subsetHelper(s, {});
}

我们可以看到，这里我们写了两个函数，其中 subsetHelper 是主要的递归函数。这是因为，在递归回溯的问题里，我们往往需要使用多个参数来记录我们已经走过的路径，但是我们不希望使用这个函数的用户提供这些参数，所以我们只让他们来提供一个集合，而设计这个函数的人去提供额外的参数。

这也是回溯算法的一个特点——回溯算法往往需要通过构造另外一个辅助函数来帮忙解决问题。

如果你对这个问题的其它延伸问题感兴趣的话，可以去搜索子集问题，你可以发现很多利用到这个思考方式——包括/不包括 某个元素——的题目。

货币问题⌗

货币问题是另一种运用递归回溯思想的题目：

在美国，就像在大多数国家一样，给任何总数的零钱最好的方法是使用一个贪婪的策略——找到面额最大但少于总数的硬币，给其中一个，然后重复。例如，在美国，支付给一个人97美分的现金，最好的策略是

    give a half dollar (50¢ given, 47¢ remain), then
    give a quarter (75¢ given, 22¢ remain), then
    give a dime (85¢ given, 12¢ remain), then
    give a dime (95¢ given, 2¢ remain), then
    give a penny (96¢ given, 1¢ remain), then
    give another penny (97¢ given, 0¢ remain).

This uses six total coins, and there’s no way to use fewer coins to achieve the same total.

然而，也有可能出现这种贪婪策略并不总是适用的硬币系统。例如，在一个奇怪的国家里，居民们出于某种奇怪的原因，决定使用1、12、14、63的面值。假设你需要返还24美分。最好的方法是返还2枚12美分的硬币。然而，在贪心策略下，总是选择面额小于总数的最大硬币，你会选择一个14美分的硬币和10个1美分的硬币，总共是15美分。这很糟糕!

你的任务是写一个递归函数 int fewestCoinsFor(int cents, Set<int>& coins)

该函数接受需要支付的面额和一个国家使用的不同面值硬币的集合作为输入，然后返回完成付款的最小硬币数量。在美国硬币的情况下，这应该总是返回与贪心方法相同的数字，但在其他情况它可能返回比贪心算法更少的硬币数量!

这个问题用如下的三个函数就可以解决：

Set<int> possibleSet(int cents, Set<int> coins){
    Set<int> s;
    for(int i : coins){
        if(i <= cents){
            s.add(i);
        }
    }
    return s;
}

void GetFewest(int cents, Set<int> coins, Set<int>& results, int n){
    if(coins.size() == 1){
        results.add(n + cents);
        return;
    }
    if(cents == 0){
        results.add(n);
        return;
    }

    n += 1;
    Set<int> usableCoins = possibleSet(cents, coins);
    for(int i : usableCoins){ //遍历每一种可能
        GetFewest(cents - i, usableCoins, results, n);
    }
}

int fewestCoinsFor(int cents, Set<int>& coins) {
    Set<int> results;
    int n = 0;
    GetFewest(cents, coins, results, n);

    return results.first();
}

首先，possibleSet 这个函数会接受一个还未完成支付的面额与一个货币系统的集合，它会返回一个集合包含还可以使用的硬币。

然后，在递归 GetFewest 的函数里，我们会遍历这个 possibleSet 所返回的集合的每一个元素。因为对于 GetFewest 函数来说，我们所需要做的决策就是选择哪一个硬币。但是由于有些地方不能总是选择最大的硬币，所以我们要尝试使用每一种硬币的可能性。

最后，我们的退出条件就是我们只有面值为1的硬币可以使用。因为，在这种情况下，我们只能使用1，所以遍历没有了意义。然后，我们会在结束条件里，把我们这个解决方案所花费的硬币储存在一个 result 的集合里。因为这个集合是通过传递地址到的 GetFewest 函数，所以在函数结束后，我们还是可以在用户调用的 fewestCoinsFor 里访问。

最最最后，我们只需要在 fewestCoinsFor 中输出 result 的第一个元素就可以了。【因为第一个元素是最小的；如果你使用的集合没有这个特性，返回最小的result即可】

七、 结语 & 一道简单的题⌗

看到这里，相信你对递归有了一定的掌握，下面你可以使用递归来解决一些更有意思的问题了！

你可以去了解一下迷宫问题，相信你会发现你好像可以解决这个问题了，去尝试一下吧！

最后，你可以用这道题检测一下自己的水平：

大约两年前，跳一跳成为了一项风靡全中国的游戏。 下面我们给出一个简化的跳跃规则： 每次玩家从当前方块跳到下一个方块时，如果没有跳到方块的中心，得1分。如果跳到方块的中心，但之前的分数是1或者这是游戏的第一次跳跃，分数是2分。否则，得分比前一次高出2分。(如果你连续跳到方块的中心，你的总得分将会是+ 2，+ 4，+ 6，+ 8…)。当玩家没有跳到方块，游戏结束。

你的程序会得到一行字符串，其中包含第一次跳跃后的分数和最后一次跳跃后的分数，以及代表游戏结束的0，这三个分数由空格分隔。你的任务是给出一个获得最终分数的可能“路径”。

例如，你可以得到这样的字符串:

1 8 0

1表示第一次跳跃后的得分为1。8表示最后一次跳跃后的总分为8。0表示游戏结束。 现在，如果给出了这个字符串，则需要输出人们可以获得最终分数的所有可能方式(即上面的字符串为8)。例如，您需要输出以下内容:

1 1 1 1 1 1 1 1 0 1 2 4 1 0 1 2 1 2 1 1 0 1 2 1 1 1 1 1 0 …省略

编写一个递归函数

void possibleProcess(string line);

它接受一个字符串作为输入，该字符串行包含第一次跳跃后的分数和总分(最后一次跳跃后的分数)，以及表示游戏结束的0，这三个分数以空格分割。该函数需要输出获得该分数的所有可能“路径”。

您的函数还应满足以下要求:

  • 可能会有无效分数，即有些第一次跳跃的分数会大于最终得分。遇到这些时，抛出一个错误。
  • 如果第一次得分或最终得分为零，简单地输出0。