第 82 / 187 篇

7.6. 递归

说明

本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C7-x86_64/recursion.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。

7.6. Recursion

递归函数是一类特殊的函数,它们调用自身(也称为自引用函数,self-referential function)来计算一个值。和非递归的函数一样,递归函数的每次调用都会创建新的栈帧。与标准函数不同的是,递归函数中包含对自身的函数调用。

Recursive functions are a special class of functions that call themselves (also known as self-referential functions) to compute a value. Like their nonrecursive counterparts, recursive functions create new stack frames for each function call. Unlike standard functions, recursive functions contain function calls to themselves.

我们再来看把从 1 到 n 的正整数加起来的问题。在前面的小节中,我们讨论了完成这项任务的 sumUp 函数。表 1 给出了一个相关的函数 sumDown,它按相反的顺序(从 n 到 1)把数加起来,还给出了与之等价的递归版本 sumr:

Let’s revisit the problem of summing up the set of positive integers from 1 to n. In previous sections, we discussed the sumUp function to achieve this task. Table 1 shows a related function called sumDown that adds the numbers in reverse (n to 1), and its recursive equivalent sumr:

表 1. 迭代版本(sumDown)与递归版本(sumr)

Table 1. Iterative version (sumDown) and recursive version (sumr)

迭代版本

Iterative

1
2
3
4
5
6
7
8
9
int sumDown(int n) {
int total = 0;
int i = n;
while (i > 0) {
total += i;
i--;
}
return total;
}

递归版本

Recursive

1
2
3
4
5
6
int sumr(int n) {
if (n <= 0) {
return 0;
}
return n + sumr(n-1);
}

递归函数 sumr 中的基本情况(base case)处理所有小于一的 n 值。递归步骤以值 n-1 调用 sumr,并在返回之前把结果加到 n 上。编译 sumr 并用 GDB 反汇编,得到如下汇编代码:

The base case in the recursive function sumr accounts for any values of n that are less than one. The recursive step calls sumr with the value n-1 and adds the result to n prior to returning. Compiling sumr and disassembling it with GDB yields the following assembly code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Dump of assembler code for function sumr:
0x400551 <+0>: push %rbp # save %rbp
0x400552 <+1>: mov %rsp,%rbp # update %rbp (new stack frame)
0x400555 <+4>: sub $0x10,%rsp # expand stack frame by 16 bytes
0x400559 <+8>: mov %edi,-0x4(%rbp) # move first param (n) to %rbp-0x4
0x40055c <+11>: cmp $0x0,-0x4(%rbp) # compare n to 0
0x400560 <+15>: jg 0x400569 <sumr+24> # if (n > 0) goto <sumr+24> [body]
0x400562 <+17>: mov $0x0,%eax # copy 0 to %eax
0x400567 <+22>: jmp 0x40057d <sumr+44> # goto <sumr+44> [done]
0x400569 <+24>: mov -0x4(%rbp),%eax # copy n to %eax (result = n)
0x40056c <+27>: sub $0x1,%eax # subtract 1 from %eax (result -= 1)
0x40056f <+30>: mov %eax,%edi # copy %eax to %edi
0x400571 <+32>: callq 0x400551 <sumr> # call sumr(result)
0x400576 <+37>: mov %eax,%edx # copy returned value to %edx
0x400578 <+39>: mov -0x4(%rbp),%eax # copy n to %eax
0x40057b <+42>: add %edx,%eax # add sumr(result) to n
0x40057d <+44>: leaveq # prepare to leave the function
0x40057e <+45>: retq # return result

上面汇编代码的每一行都加上了英文注解。表 2 给出了对应的 goto 形式,以及不含 goto 语句的 C 程序:

Each line in the preceding assembly code is annotated with its English translation. Table 2 shows the corresponding goto form and C program without goto statements:

表 2. sumr 汇编代码的 C goto 形式及其翻译

Table 2. C goto form and translation of sumr assembly code

C goto 形式

C goto form

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int sumr(int n) {
int result;
if (n > 0) {
goto body;
}
result = 0;
goto done;
body:
result = n;
result -= 1;
result = sumr(result);
result += n;
done:
return result;
}

不含 goto 语句的 C 版本

C version without goto statements

1
2
3
4
5
6
7
8
9
int sumr(int n) {
int result;
if (n <= 0) {
return 0;
}
result = sumr(n-1);
result += n;
return result;
}

尽管这个翻译乍一看与原来的 sumr 函数并不完全相同,但仔细检查就会发现,两个函数确实是等价的。

Although this translation may not initially appear to be identical to the original sumr function, close inspection reveals that the two functions are indeed equivalent.

7.6.1. 动画:观察调用栈如何变化

7.6.1. Animation: Observing How the Call Stack Changes

作为练习,我们鼓励你把栈画出来,看看其中的值是如何变化的。下面的动画描绘了用值 3 运行这个函数时栈是如何更新的。

As an exercise, we encourage you to draw out the stack and see how the values change. The animation below depicts how the stack is updated when we run this function with the value 3.

recursion