说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C9-ARM64/recursion.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
9.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)累加这些数,以及与它等价的递归函数:
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 calledsumDown, which adds the numbers in reverse (n to 1), and its recursive equivalent:
表 1. sumDown 函数的迭代版本与递归版本
Table 1. Iterative and recursive version of the sumDown function.
迭代版本
Iterative
1 | int sumDown(int n) { |
递归版本
Recursive
1 | int sumr(int n) { |
递归函数 sumr 中的基本情形处理所有小于或等于零的 n 值,递归步骤则把 n 的当前值加到以 n - 1 调用 sumr 的结果上。编译 sumr 并用 GDB 反汇编,得到下面的汇编代码:
The base case in the recursive function
sumraccounts for any values of n that are less than or equal to zero, and the recursive step adds the current value of n to the result of the function call tosumrwith the value n - 1. 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 (left) and C program withoutgotostatements (right):
表 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.
9.6.1. 动画:观察调用栈如何变化
9.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.
