说明
本文是个人学习用的非官方中英对照译文,原文: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
sumUpfunction to achieve this task. Table 1 shows a related function calledsumDownthat adds the numbers in reverse (n to 1), and its recursive equivalentsumr:
表 1. 迭代版本(sumDown)与递归版本(sumr)
Table 1. Iterative version (sumDown) and recursive version (sumr)
迭代版本
Iterative
1 | int sumDown(int n) { |
递归版本
Recursive
1 | int sumr(int n) { |
递归函数 sumr 中的基本情况(base case)处理所有小于一的 n 值。递归步骤以值 n-1 调用 sumr,并在返回之前把结果加到 n 上。编译 sumr 并用 GDB 反汇编,得到如下汇编代码:
The base case in the recursive function
sumraccounts for any values of n that are less than one. The recursive step callssumrwith the value n-1 and adds the result to n prior to returning. Compilingsumrand disassembling it with GDB yields the following assembly code:
1 | Dump of assembler code for function sumr: |
上面汇编代码的每一行都加上了英文注解。表 2 给出了对应的 goto 形式,以及不含 goto 语句的 C 程序:
Each line in the preceding assembly code is annotated with its English translation. Table 2 shows the corresponding
gotoform and C program withoutgotostatements:
表 2. sumr 汇编代码的 C goto 形式及其翻译
Table 2. C goto form and translation of sumr assembly code
C goto 形式
C goto form
1 | int sumr(int n) { |
不含 goto 语句的 C 版本
C version without goto statements
1 | int sumr(int n) { |
尽管这个翻译乍一看与原来的 sumr 函数并不完全相同,但仔细检查就会发现,两个函数确实是等价的。
Although this translation may not initially appear to be identical to the original
sumrfunction, 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.
