Recursion in Programming | 编程中的递归

📚 Recursion in Programming | 编程中的递归

Recursion is a programming technique where a function calls itself to solve a smaller instance of the same problem. It is a cornerstone of algorithmic thinking, heavily examined in Edexcel A-Level Computer Science, particularly in topics like data structures, searching, and problem-solving. Mastering recursion means understanding the call stack, base cases, and how a complex problem can be reduced elegantly to a set of simple, repetitive steps.

递归是一种编程技术，函数通过调用自身来解决同一问题的更小实例。它是算法思维的核心基石，在Edexcel A-Level计算机科学考试中占有重要地位，尤其涉及数据结构、搜索和问题求解等主题。掌握递归意味着深刻理解调用栈、基准情形，以及如何将复杂问题优雅地化简为一组简单、重复的步骤。

1. What Is Recursion? | 什么是递归？

Recursion occurs when a subroutine invokes itself during its execution. Each recursive call works on a reduced version of the original input until a terminating condition, known as the base case, is met. Without a properly defined base case, recursion would continue indefinitely, leading to a stack overflow error. In Edexcel papers, you will be expected to identify how many times a recursive function calls itself and trace the sequence of calls step by step.

当一个子程序在执行过程中调用自身时，就发生了递归。每一次递归调用都处理原始输入的简化版本，直到满足一个称为基准情形的终止条件。如果没有正确定义基准情形，递归将无限进行下去，最终导致栈溢出错误。在Edexcel考试中，你需要能够识别一个递归函数调用了自身多少次，并逐步追踪调用顺序。

2. Basic Structure of Recursion | 递归的基本结构

Every recursive function consists of two essential parts: the base case and the recursive case. The base case provides the non-recursive escape route, typically handling the simplest possible input. The recursive case breaks the problem down and calls the function again with a modified argument that moves steadily toward the base case. For example, in a function to compute the sum of the first N natural numbers, the base case is N = 0 (sum is 0), and the recursive case is N + sum(N-1).

每个递归函数都由两个基本部分组成：基准情形和递归情形。基准情形提供非递归的退出路径，通常处理最简单的输入。递归情形则将问题分解，并用一个逐步靠近基准情形的修改后的参数再次调用函数。例如，在计算前N个自然数之和的函数中，基准情形是 N = 0（和为0），递归情形是 N + sum(N-1)。

A typical template in pseudocode can be represented as:

递归伪代码的典型模板可表示为：

function recursive(input)
if input is base case then
return base value
else
return some operation involving recursive(smaller input)
end if
end function

3. How Recursion Works: The Call Stack | 递归如何工作：调用栈

When a function calls itself, the current execution pauses, and its state (local variables, return address) is pushed onto the call stack. A new stack frame is created for the next call. This process repeats until the base case is reached. At that point, the stack begins to unwind: each frame is popped, and the returned value is used to compute the result for the previous level. The Edexcel specification often asks students to draw the call stack during a recursive process, particularly for procedures with multiple recursive calls, such as calculating Fibonacci numbers.

当函数调用自身时，当前执行暂停，其状态（局部变量、返回地址）被压入调用栈。为下一次调用创建一个新的栈帧。这一过程不断重复，直到达到基准情形。此时，栈开始收缩：每个栈帧被弹出，返回值用于计算上一级的结果。Edexcel大纲经常要求学生画出递归过程中的调用栈，尤其是像计算斐波那契数这样具有多次递归调用的过程。

Stack Frame Level	Function Call	Local State
1 (top)	factorial(1)	n = 1, waiting for factorial(0)
2	factorial(2)	n = 2, waiting for factorial(1)
3	factorial(3)	n = 3, waiting for factorial(2)

This table illustrates the stack after calling factorial(3). Once factorial(0) returns 1, each frame multiplies its n by the returned value and passes the result upward.

上表展示了调用 factorial(3) 后的栈状态。一旦 factorial(0) 返回 1，每个栈帧将自己的 n 与返回值相乘，并将结果向上传递。

4. Recursion vs. Iteration | 递归与迭代

Any problem solvable recursively can also be implemented using iteration (loops). The key differences lie in memory usage, readability, and performance. Recursive solutions are often more elegant and closely mirror the mathematical definition, but they carry overhead from repeated function calls and stack memory consumption. Iterative solutions usually run faster and use less memory because they avoid the call stack overhead, though they may involve more complex control flow. Edexcel exam questions frequently require candidates to convert a simple recursive function into an iterative one and vice versa.

任何可以用递归解决的问题也可以用迭代（循环）实现。关键区别在于内存使用、可读性和性能。递归解决方案往往更优雅，贴近数学定义，但会因重复的函数调用和栈内存消耗而产生额外开销。迭代解决方案通常运行更快且占用更少内存，因为它们避免了调用栈带来的开销，尽管可能涉及更复杂的控制流。Edexcel考试题目经常要求考生将简单的递归函数转化为迭代函数，反之亦然。

A classic comparison for factorial:

Iterative: use a loop to multiply 1 × 2 × … × n.
Recursive: define n! = n × (n-1)! with base case 0! = 1.

经典对比——阶乘：

迭代：使用循环计算 1 × 2 × … × n。
递归：定义 n! = n × (n-1)!，基准情形 0! = 1。

5. Classic Example: Factorial | 经典例子：阶乘

The factorial function is the simplest instructive example of recursion. The mathematical definition is naturally recursive:

阶乘函数是递归最简单、最具启发性的例子。其数学定义天然就是递归的：

n! = n × (n-1)! for n > 0, and 0! = 1

A pseudo‑code implementation can be written as:

伪代码实现如下：

function factorial(n)
if n ≤ 0 then
return 1
else
return n × factorial(n – 1)
end if
end function

Tracing factorial(4) generates the following sequence of calls and returns:

factorial(4) → 4 × factorial(3)
factorial(3) → 3 × factorial(2)
factorial(2) → 2 × factorial(1)
factorial(1) → 1 × factorial(0)
factorial(0) → 1 (base case)

Then the multiplications unwind: 1×1=1, 2×1=2, 3×2=6, 4×6=24.

追踪 factorial(4) 产生以下的调用与返回序列：

factorial(4) → 4 × factorial(3)
factorial(3) → 3 × factorial(2)
factorial(2) → 2 × factorial(1)
factorial(1) → 1 × factorial(0)
factorial(0) → 1（基准情形）

随后乘法回卷：1×1=1，2×1=2，3×2=6，4×6=24。

6. Fibonacci Sequence: Pitfalls of Recursion | 斐波那契数列：递归的陷阱

The Fibonacci sequence is defined recursively as Fib(n) = Fib(n‑1) + Fib(n‑2) for n > 1, with Fib(0)=0 and Fib(1)=1. While this definition is mathematically elegant, a naive recursive implementation is highly inefficient because it recalculates the same values many times, exhibiting exponential time complexity O(2ⁿ). This makes it a perfect example to teach the limitations of recursion and the need for optimisation techniques like memoisation or dynamic programming.

斐波那契数列的递归定义为：对于 n > 1，Fib(n) = Fib(n-1) + Fib(n-2)，且 Fib(0)=0，Fib(1)=1。虽然这一定义在数学上十分优雅，但朴素的递归实现效率非常低，因为它会多次重复计算相同的值，呈现出指数时间复杂度 O(2ⁿ)。这使其成为讲解递归局限性和需要记忆化或动态规划等优化技术的完美实例。

To compute Fib(5), the call tree contains 15 function calls; for Fib(10), it already requires 177 calls. In an exam you may be asked to calculate the number of calls or to improve an existing recursive Fibonacci function using a lookup table.

为计算 Fib(5)，调用树包含 15 次函数调用；计算 Fib(10) 则需要 177 次调用。在考试中，你可能需要计算调用次数，或者使用查找表改进现有的递归斐波那契函数。

7. Tail Recursion Optimisation | 尾递归优化

Tail recursion is a special case where the recursive call is the last operation before the function returns; there is no pending computation after the call. In such cases, the compiler or interpreter can reuse the same stack frame instead of adding a new one, transforming recursion into iteration under the hood. This eliminates the risk of stack overflow and improves performance. For example, a tail‑recursive factorial function passes an accumulator:

尾递归是一种特殊情况：递归调用是函数返回前执行的最后一个操作，调用之后没有任何待执行的计算。在这种情况下，编译器或解释器可以重用同一个栈帧而不必新增一个，从而在底层将递归转化为迭代。这消除了栈溢出的风险并提高性能。例如，一个尾递归的阶乘函数可借助累加器实现：

function factorialTail(n, acc = 1)
if n ≤ 0 then
return acc
else
return factorialTail(n‑1, acc × n)
end if
end function

Not all programming languages support automatic tail call optimisation (TCO), but functional languages like Haskell and Scheme do. Edexcel questions on recursion rarely demand deep TCO knowledge, but being aware of accumulator‑based recursion can help you design more efficient recursive solutions.

并非所有编程语言都支持自动尾调用优化（TCO），但像 Haskell 和 Scheme 这样的函数式语言支持。Edexcel 关于递归的试题很少要求深入的 TCO 知识，但了解基于累加器的递归有助于设计出更高效的递归解决方案。

8. Recursion in Algorithms: Divide and Conquer & Searching | 递归在算法中的应用：分治与搜索

Recursion is the natural tool for divide‑and‑conquer algorithms such as merge sort, quick sort, and binary search. In binary search, the problem space is halved with each recursive call: the algorithm compares the middle element with the target and then recursively searches either the left or right sub‑array until the element is found or the sub‑array is empty. This gives a logarithmic time complexity O(log n). The recursive formula for binary search is:

递归是实现分治算法（如归并排序、快速排序和二分搜索）的自然工具。在二分搜索中，问题空间在每次递归调用时缩小一半：算法将中间元素与目标比较，然后递归地搜索左半部分或右半部分，直到找到目标或子数组为空。这带来了对数时间复杂度 O(log n)。二分搜索的递归公式为：

binarySearch(array, low, high, target):
if low > high then return -1
mid = (low + high) / 2
if array[mid] = target then return mid
else if array[mid] > target then
return binarySearch(array, low, mid‑1, target)
else
return binarySearch(array, mid+1, high, target)
end if

Understanding the recursion tree of divide‑and‑conquer algorithms is essential for analysing their time complexity using recurrence relations.

理解分治算法的递归树对于使用递推关系分析它们的时间复杂度至关重要。

9. Traversing Recursive Data Structures: Binary Trees | 遍历递归数据结构：二叉树

Data structures defined recursively, such as binary trees, are traversed most naturally using recursion. A binary tree node consists of a value, a left subtree, and a right subtree. The three standard depth‑first traversals — pre‑order, in‑order, and post‑order — are expressed with just a few lines of recursive code. For example, an in‑order traversal visits the left subtree, then the node, then the right subtree:

递归定义的数据结构（如二叉树）最适合使用递归进行遍历。一个二叉树节点由一个值和左右两个子树组成。三种标准的深度优先遍历——前序、中序和后序——仅用几行递归代码即可表达。例如，中序遍历访问左子树，然后访问节点，最后访问右子树：

procedure inOrder(node)
if node is not null then
inOrder(node.left)
visit(node)
inOrder(node.right)
end if
end procedure

Edexcel often examines the ability to apply recursive thinking to tree‑based problems, such as computing the height of a tree, counting nodes, or checking for a binary search tree property. Being fluent in recursive tree traversal is a fundamental skill for the A-Level programming paper.

Edexcel 经常考查将递归思维应用于树相关问题的能力，例如计算树的高度、统计节点数目或检查二叉搜索树的性质。熟练运用递归进行树遍历是 A-Level 编程试卷的一项基本技能。

10. Pros, Cons, and Exam Tips | 递归的优缺点与考试技巧

Recursion offers clean, maintainable code for problems that have a naturally repetitive hierarchical structure. It simplifies the implementation of algorithms that would be convoluted with loops. However, recursion can lead to inefficient memory usage, stack overflow for deep recursions, and potential performance problems when not optimised. In an Edexcel exam, you should be able to:

Trace a recursive algorithm by hand, showing each call and return value.
Identify the base case and recursive case in a given code snippet.
Convert between recursive and iterative implementations.
Analyse the efficiency of a recursive solution, particularly for Fibonacci‑style overlapping subproblems.
Apply recursion to standard algorithms (binary search, tree traversals).

递归为具有天然层次重复结构的问题提供了简洁、可维护的代码。它简化了那些用循环表达会变得复杂的算法的实现。然而，递归可能导致内存使用效率低下，深层递归会造成栈溢出，并且未经优化时可能带来性能问题。在 Edexcel 考试中，你应该能够：

手动追踪一个递归算法，展示每次调用和返回值。
在给定的代码片段中识别基准情形和递归情形。
在递归实现和迭代实现之间进行转换。
分析递归解决方案的效率，特别是对于斐波那契类重叠子问题。
将递归应用于标准算法（二分搜索、树遍历）。

When tackling a written trace question, use a stack‑based approach: draw a table for each active call, record local variables, and simulate the unwinding systematically. This will help you avoid mistakes with multiple recursive calls and earn full marks on structured paper questions.

在处理文字追踪题时，采用基于栈的方法：为每次活动调用绘制一个表格，记录局部变量，并系统地模拟回卷过程。这将帮助你避免在多次递归调用时出错，并在结构化试卷题目中获得满分。

Published by TutorHao | Programming Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Recursion in Programming | 编程中的递归