文章也同时在简书更新

背景

今天微机张教授给我看了一道考研的数据结构题，是华南理工大学的，引起了我的兴趣。

原题和分析如下：

~~其实我很不喜欢刷题，所以面试裸考经常悲剧。~~

回归正题，这属于一道考察递归知识的题目，如果大家和我一样，对于题目下方的分析不是很理解，那么本文的价值就来了。

递归和迭代

首先介绍一下递归，递归（英语：recursion）在计算机科学中是指一种通过重复将问题分解为 同类的子问题 而解决问题的方法。具体含义可以戳这里：递归 (计算机科学))。

这里的 同类的子问题 一语中的，根据我的理解，递归其实是迭代的一种实现方式，迭代可以理解为我们常说的for语句，递归则是所谓的“函数里面调用函数本身”。

大部分递归都可以较为容易地转换成迭代。二者都是基于某一初始条件和终止条件进行的循环计算，递归的好处是便于实现，根据数学公式可以方便地写出递归算法，但相应的计算机运行效率会较低，而且递归次数过多会爆栈。相比之下迭代需要更多的思考技巧，但效率也会更好（前提是你的算法是合理的）。

对于计算阶乘这个问题，下面分别是递归和迭代两种实现：

递归

long long factorial_recurse (int n)
{
    if (n > 1) {
        return n * factorial_recurse(n-1);
    }
    if (n == 1) {
        return 1;
    }
    return -1; //should never go here
}

迭代

long long factorial_iteration (int n)
{
    long long res = 1;
    while (n) {
        res *= n;
        n--;
    }
    return res;
}

可以看到，递归这时并没有带来思考上的便利，反而还会降低计算上的效率。

解题

上文主要让大家快速了解一下基本概念，现在我们还没有分析题目，下面开始。

首先就解题而言，因为只是f(4)，递归次数不多，我们只要一步一步做就行。解题过程如下：

f0: return;
=>  nothing
f1: print 1;  //1
    f0;       //nothing
    f0;       //nothing
=>  1
f2: print 2   //2
    f1;       //1
    f1;       //1
=> 2, 1, 1
f3: print 3   //3
    f2;       //2, 1, 1  
    f2;       //2, 1, 1
=>  3, 2, 1, 1, 2, 1, 1
f4: print 4   //4
    f3;       //3, 2, 1, 1, 2, 1, 1
    f3;       //3, 2, 1, 1, 2, 1, 1
=>  4, 3, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 2, 1, 1

按照步骤慢慢来，是可以笔算做好的。

分析

但本文是要给大家讲清楚其内部原理，因此按照传统，后文会从底层汇编来看一下。

在此之前，你可能需要知道：

递归与函数地址压栈和出栈有关，后文统一用push，pop代替。
取得任意一条指令的地址后，在执行该指令前，都会被送往CS:IP寄存器，以标记当前正在执行的指令的地址。
执行一个函数前，先从CS:IP寄存器中取出当前指令地址A，把A的下一条指令地址B，即函数断口地址push压栈，函数执行完，pop出断口地址B，把B给CS:IP，继续后续执行。
所谓断口地址，就是当前汇编指令之后的下一条指令的地址，此处可以理解为函数执行完后，后续程序指令的地址。

为了方便理解，我们用下述较为简单的代码讲解：

void fff(int k)
{
    if (k>0) {
        printf("before push k: %d\\\\n", k);
        fff(k-1);
        printf("after  pop  k: %d\\\\n", k);
    }
}

执行f(4)的输出结果如下：

before push k: 4
before push k: 3
before push k: 2
before push k: 1
after  pop  k: 1
after  pop  k: 2
after  pop  k: 3
after  pop  k: 4

可以看到一个上下对称的输出，其中正是push和pop的体现。可以结合下图左侧的堆栈信息，产生一个更直观的印象，如下：

深入底层

我们来看一下函数void fff(int)的汇编代码，这里我去掉了printf这部分代码的干扰：

Recurse_Test fff:
    0x100000dc0 <+0>:  pushq  %rbp
    0x100000dc1 <+1>:  movq   %rsp, %rbp
    0x100000dc4 <+4>:  subq   $0x10, %rsp
    0x100000dc8 <+8>:  movl   %edi, -0x4(%rbp)
    0x100000dcb <+11>: cmpl   $0x0, -0x4(%rbp)
    0x100000dcf <+15>: jle    0x100000de2               ; <+34> at main.c:71
->  0x100000dd5 <+21>: movl   -0x4(%rbp), %eax
    0x100000dd8 <+24>: subl   $0x1, %eax
    0x100000ddb <+27>: movl   %eax, %edi
    0x100000ddd <+29>: callq  0x100000dc0               ; <+0> at main.c:65
    0x100000de2 <+34>: addq   $0x10, %rsp
    0x100000de6 <+38>: popq   %rbp
    0x100000de7 <+39>: retq   
    0x100000de8 <+40>: nopl   (%rax,%rax)

首先，注意到开头<+0>处的pushq和结尾<+38>处的popq，它们分别表示执行任何一个函数体，都要先把函数的断口地址push进去，执行完后pop回来。

可以看到push和pop有关的函数的断口地址0x100000dc0是放在寄存器里面的。之后会通过这个地址找到后续要执行的函数的实现（这让我想起了OC Runtime的IMP指针，哈哈）。

函数首地址通过pushq指令被push后，就会进入函数体，执行函数内的代码，待函数执行完毕，注意<+15>处，汇编代码会执行jle指令跳转到<+34>处，即popq指令前，然后函数断口地址被pop，表明函数生命周期结束，程序继续执行其他内容。

如果含有递归，注意<+29>处的callq指令，它调用的地址就是被push的函数的断口地址0x100000dc0，而这个断口地址下一步执行的仍旧是该函数（只是所带的参数不同），于是就发生了函数内部调用函数本身，即递归。递归也是一次函数调用，一样会走到<+0>处的pushq，执行完后也要popq。但递归会在函数返回前继续执行函数本身，似乎不会返回，其实它在等待一个 终止条件 ，一旦条件到达，递归就会开始pop之前push进去的“函数们”。

而这里的终止条件就是：当k＝＝0时，代码逻辑不会走if语句，此时函数（现在是f0）就会return，执行popq指令。之后前面被push的f3, f2, f1就会依次pop，执行的相应的popq指令。当最开始的f3被pop结束后，外层的f4函数就正式执行完毕了。

一次递归调用f(4)的流程大致就是这样，大家可以真机运行一下，会更容易理解。

小结

以上就是关于递归的一些理解，希望能帮助到大家。
欢迎大家转载！

That’s all. Thanks for reading.

微信公众号

第一时间获取最新内容，欢迎关注微信公众号：「洛斯里克的大书库」。