Recursion in A-Level Programming | A-Level 编程中的递归

📚 Recursion in A-Level Programming | A-Level 编程中的递归

Recursion is one of the most powerful problem-solving tools in A-Level programming. It allows a function to call itself to break down complex problems into smaller, identical subproblems. This article explains the core ideas, common examples, and exam-ready techniques required by Edexcel.

递归是 A-Level 编程中最强大的问题求解工具之一。它允许函数调用自身，将复杂问题分解为更小、结构相同的子问题。本文讲解核心思想、常见示例以及 Edexcel 考试所需的技巧。

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

A recursive function is a function that calls itself within its own definition. It keeps calling itself with modified arguments until a stopping condition is reached. This stopping condition is called the base case.

递归函数是在自身定义中调用自己的函数。它持续使用修改后的参数调用自身，直到满足停止条件。这个停止条件称为基准情形。

Recursion works well when a problem can be broken down into smaller subproblems of the same type. Examples include calculating factorials, traversing tree structures, and sorting lists. The main benefit is that the code often mirrors the mathematical definition closely.

当一个问题可以分解为相同类型的更小子问题时，递归非常有效。示例包括计算阶乘、遍历树结构和对列表排序。主要优点是代码往往与数学定义高度一致。

2. Base Case and Recursive Case | 基准情形与递归情形

Every correct recursive function must have at least one base case and one recursive case. The base case returns a value directly without making any further recursive calls. The recursive case reduces the problem size and calls the same function again with a smaller input.

每个正确的递归函数必须至少有一个基准情形和一个递归情形。基准情形直接返回一个值，不再进行任何递归调用。递归情形缩小问题规模，并使用更小的输入再次调用同一个函数。

A common exam question asks you to identify both cases in a given piece of pseudocode. The base case is the branch that does not call the function again, and the recursive case is the branch that does.

常见的考试题目要求你在给定的伪代码中识别这两种情形。基准情形是不再调用函数的分支，而递归情形是会再次调用函数的分支。

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

3. The Call Stack | 调用栈

When a recursive function runs, the computer uses a call stack to manage function calls. Each call creates a new stack frame containing local variables, parameters, and the return address. These frames are pushed onto the stack as calls are made.

递归函数运行时，计算机使用调用栈来管理函数调用。每次调用都会创建一个新的栈帧，其中包含局部变量、参数和返回地址。这些栈帧在调用发生时被推入栈中。

Once the base case is reached, the function returns a value. The stack then unwinds, or pops frames one by one, using each returned value to compute the next result. This LIFO (last in, first out) behaviour is essential for recursion.

一旦达到基准情形，函数就会返回一个值。然后栈开始展开，即逐个弹出栈帧，并使用每个返回值计算下一个结果。这种后进先出 LIFO 行为对递归至关重要。

A stack frame is removed when the function returns. If too many frames are pushed, the stack can run out of space. This is why infinite recursion leads to a stack overflow error.

当函数返回时，栈帧被移除。如果推入过多的栈帧，栈空间可能耗尽。这就是无限递归导致栈溢出错误的原因。

4. Factorial Example | 阶乘示例

The factorial function is a classic introduction to recursion. It is defined as factorial(n) = n × factorial(n – 1), with the base case factorial(0) = 1. For example, factorial(4) expands to 4 × 3 × 2 × 1, which equals 24.

阶乘函数是递归的经典入门示例。它定义为 factorial(n) = n × factorial(n – 1)，基准情形为 factorial(0) = 1。例如，factorial(4) 展开为 4 × 3 × 2 × 1，结果为 24。

A trace of factorial(4) shows the call stack growing and then shrinking. The calls are factorial(4), factorial(3), factorial(2), factorial(1), factorial(0). The returns multiply in reverse order to produce 24.

跟踪 factorial(4) 可以看到调用栈先增长后收缩。调用序列为 factorial(4)、factorial(3)、factorial(2)、factorial(1)、factorial(0)。返回值按相反顺序相乘，得到 24。

0! = 1 and n! = n × (n – 1)! for n &gt