如何理解递归（一）

递归是程序运行时的一种现象，也是解决某些特定问题时较迭代算法来说更自然更优雅的代码组织方式。作为程序员工作了多年后，我发现一个能不能理解好递归，能不能用递归来解决问题是区分程序员和非程序员，甚至于区分好程序员和差程序员的试金石。很多人通过学习掌握了某些语言的语法，也能写一些代码，但是一遇递归就头大。我曾经也是经历过这样的一段时间，所以希望这篇文多少能对这样的人有点帮助。

谈到递归，程序设计课程老师可能会说递归就是「函数自己调用自己」。比如下面的代码段：

void foo()
{
    // 自己调用自己就是递归
    foo();
}

我们知道这个函数要是运行起来，除了让你的程序报出一个「堆栈溢出」的错误外，其他什么作用也没有。在某种程度上说，我们的大脑就是一个计算机。当我们尝试去理解「自己调用自己」这句话时，大脑也会陷入一个无限的递归过程里，然后「轰」的一声「堆栈溢出」了，所以也就无法去理解了。当然老师还会告诉你递归除了「自己调用自己」外，还有很重要的一部分就是在满足条件的时候函数会返回，这样就避免出现无限递归的过程了。所以一个完整的递归函数组成如下：

void foo()
{
    // 返回部分
    if (condition)
    {
        return;
    }
    
    // 递归部分
    foo();
}

接下来老师一般会举例如何用递归计算斐波那契数列数列，反正当初我们的算法老师就是这样教的。要是你不了解什么是斐波那契数列，可以自己百度或谷歌一下。一般计算该数列的代码段如下：

unsigned int fibo(unsigned int n)
{
    // 返回部分
    if (n == 0)
        return 0;
    if (n == 1) {
        return 1;
    }
    
    // 递归部分
    return fibo(n - 1) + fibo(n - 2);
}

到这里老师大概就会来个总结陈词，你看这就是递归的用处了，它可以很优雅的解决这样的问题。但是有多少人是真的理解的呢？反正我自己在学的时候，完全是懵掉的，而且一直持续到工作很多年。有一段时间我甚至觉得递归只是用来计算斐波那契数列的……

要理解递归，我们要退一步，了解另一个概念——「分而治之」。稍微了解程序设计的人，对这个概念应该不陌生。通俗的说，假如我们有这样一个问题A，如果能把A分解成一系列比A更容易解决的子问题（A0，A1，A2……An），通过解决子问题（A0，A1，A2……An）来最终达成解决问题A，这个就是「分而治之」。从本质上来说递归就是「分而治之」概念的一个应用。以递归计算斐波纳切数列来举例，要计算斐波纳切数列的第n项该怎么办？通过数列的定义我们知道第n项的值等于第n-1项加上第n-2项，所以我们可以把计算第n项这个问题分解成计算n-1项和n-2项两个子问题。我们知道计算n-1和n-2项要比计算n项更容易点（因为n-1和n-2都比n要来得小）。那么n-1项由如何计算呢？根据定义n-1项等于（n-1）- 1项和（n-1）-2项的值，好了，我们在这里碰到了递归，好，我们先就此打住。因为n在一直减少，最终会减到1，再减到0，而第0项和第1项的值我们不用计算就知道的，这就是递归终结的时候了。

通用概括一下，在面对递归问题时，我们可以用「分而治之」的概念去帮助理解。步骤如下：

1. 把问题分解成更容易解决的子问题集合，比如可以把计算斐波那契数列的第n项问题分解转换成计算第n-1项加上第n-2项这两个子问题
2. 假设我们有一个函数可以应用在所有的子问题上，比如计算斐波那契数列的fibo函数
3. 基于步骤2的函数，实现如何把子问题的解拼成最终问题的解，这就是递归部分，在计算斐波那契数列的例子里就是fibo(n-1) + fibo(n-2)部分
4. 递归部分确定了，然后再考虑子问题最终简化到到最底层时该返回什么值。
5. 上面4步都做好了之后，剩下的就只是毫无条件的相信计算机了……

根据上面的步骤我们来尝试一下解决下面这个很常见的面试题目：「实现一个函数翻转给定的字符串」。假设我们要翻转的字符串是「abcdef」，那么翻转之后的结果应该是「fedcba」。毫无疑问这个字符串我们是没办法一下子就翻转过来的，那么「分而治之」吧。我们不能把多个字符一下子就完全翻转过来，但是假如字符串里的字符只有一个呢？我们翻转起来最方便了，因为什么都不用做。好了，我们可以把「abcdef」分解成「a」和「bcdef」两个子字符串。「bcdef」比「abcdef」短一个字符，理论上也稍微容易点。假设我们有这样的函数能接受一个字符串，然后像变戏法一样就能返回一个翻转后的字符串，如下：

string revertString(const string& str)
{
    // 戏法
}

那么有了这个函数之后，我们怎么应用这个函数把「a」和「bcdef」组合成最后的结果呢？很简单我们只要把「a」加到「bcdef」的翻转字符串后面去就可以了，如下：

string revertString(const string& str)
{
    // str = 'abcdef'
    // str[0] = 'a'
    // str.substr(1) = 'bcdef'
    return revertString(str.substr(1)) + str[0];
}

当然现在这个函数还不能直接交给计算机去执行，因为我们传给revertString的参数字符串在不断的缩短，当缩短到一个字符或者一个字符也没有时，我们就没办法再继续缩短了，我们要把这些情况也处理掉才行：

string revertString(const string& str)
{
    if (str.length() <= 1) {
        return str;
    }
    // str = 'abcdef'
    // str[0] = 'a'
    // str.substr(1) = 'bcdef'
    return revertString(str.substr(1)) + str[0];
}

好了，这样的一个函数就可以交给计算机去执行了，然后剩下的事情就是「见证奇迹」的时刻了。以上的思维过程可以应用于绝大多数递归算法上。作为练习，读者朋友可以尝试用递归来解决另一个常见的算法面试问题：如何判断一个字符串是否是回文。友情提示，可以把问题分解成判断头尾两个字符和除了头尾之外的子字符串都是否符合回文条件。

用递归来解决问题，在代码组织上毫无疑问是很优雅的，但是在时间和空间的复杂度上往往不是最优的，如何解决这个问题，我将在接下来的一篇文里跟大家聊一聊。