1. 引言
在本篇教程中，我们将深入探讨直接递归（Direct Recursion）与间接递归（Indirect Recursion）的概念与区别。这两个概念是编程中递归思想的两种基本实现方式，掌握它们有助于我们更高效地编写递归逻辑，避免踩坑。
2. 递归概述
递归是一种函数调用自身来解决问题的编程方法。它在解决分治、回溯、树形结构遍历等问题时非常有效，但同时也容易引发栈溢出、无限递归等常见问题。
一个完整的递归函数必须包含两个部分：
- ✅ 基准条件（Base Case）：用于终止递归调用，防止无限循环。
- ✅ 递归条件（Recursive Case）：函数调用自身的逻辑，通常会对输入参数进行缩减。
下面是一个简单的递归示例，用于计算一个整数列表的总和：
algorithm sumMyList(myList, size):
// INPUT
// myList = List of numbers
// size = Size of the list
// OUTPUT
// Returns the sum of elements in myList
if size <= 0:
return 0
else:
return myList[size - 1] + sumMyList(myList, size - 1)
在这个例子中：
- 基准条件是
if size <= 0，当列表为空时递归结束。 - 递归条件是
return myList[size - 1] + sumMyList(...)，每次递归都会减少列表的大小，直到满足基准条件为止。
使用递归时，必须确保最终能到达基准条件，否则将导致栈溢出或程序崩溃。接下来我们将分别介绍直接递归和间接递归。
3. 直接递归
直接递归是指一个函数在其函数体内直接调用自己。这是最常见的递归形式，逻辑结构清晰，易于理解和实现。
举个例子，计算一个整数的阶乘（factorial）就是典型的直接递归场景：
algorithm findFactorial(number):
// INPUT
// number = A positive integer
// OUTPUT
// Returns the factorial of the number
if number == 1:
return 1
else:
return number * findFactorial(number - 1)
在这个函数中：
- 基准条件是
if number == 1。 - 递归条件是
return number * findFactorial(number - 1)，每次递归调用自身，参数减1。
3.1 直接递归的优缺点
✅ 优点：
- 实现简单，逻辑集中在一个函数中。
- 没有额外函数调用开销，效率较高（在递归深度不大的情况下）。
❌ 缺点：
- 调试困难，递归层级深时调用栈会非常复杂。
- 若没有正确设置基准条件，极易造成栈溢出。
⚠️ 注意：对于递归深度较大的场景，建议优先考虑迭代或尾递归优化（Java 不支持尾递归）。
4. 间接递归
间接递归是指多个函数相互调用形成递归调用链。通常是一个函数调用另一个函数，而另一个函数又调用回第一个函数，形成循环调用。
例如，判断一个数是奇数还是偶数，可以通过两个函数互相调用来实现：
algorithm isEven(numb):
// INPUT
// numb = A positive integer
// OUTPUT
// Returns true if numb is even, false otherwise
if numb == 0:
return true
else:
return isOdd(numb - 1)
algorithm isOdd(numb):
// INPUT
// numb = A positive integer
// OUTPUT
// Returns true if numb is odd, false otherwise
if numb == 0:
return false
else:
return isEven(numb - 1)
在这个例子中：
isEven调用isOdd。isOdd又调用isEven。- 直到
numb == 0时递归终止。
示例执行过程：
// 示例 1: isEven(3)
isEven(3)
→ isOdd(2)
→ isEven(1)
→ isOdd(0)
→ return false
// 示例 2: isEven(4)
isEven(4)
→ isOdd(3)
→ isEven(2)
→ isOdd(1)
→ isEven(0)
→ return true
这个例子展示了间接递归的执行流程，直到基准条件成立为止。
4.1 间接递归的优缺点
✅ 优点：
- 分工明确，逻辑拆分更清晰，便于调试。
- 更适合复杂逻辑拆分，提高模块化程度。
❌ 缺点：
- 实现略复杂，多个函数之间相互依赖。
- 多次函数调用可能导致栈空间占用更大。
⚠️ 建议：在需要逻辑拆分或状态流转的场景中，可以考虑使用间接递归；否则优先使用直接递归以简化逻辑。
5. 直接递归 vs 间接递归 对比
| 比较维度 | 直接递归 | 间接递归 |
|---|---|---|
| 基准条件/递归条件定义位置 | 在同一个函数内定义 | 在不同函数中定义 |
| 递归启动方式 | 函数直接调用自己 | 一个函数调用另一个函数，再调回自己 |
| 优点 | 简洁、高效 | 可读性强、便于调试 |
| 缺点 | 调试困难、易栈溢出 | 实现复杂、调用开销大 |
6. 总结
本文我们介绍了直接递归与间接递归的基本概念、实现方式及其优缺点，并通过示例代码进行了演示。
- ✅ 直接递归：函数直接调用自己，适用于逻辑简单、递归层级不深的场景。
- ✅ 间接递归：多个函数相互调用形成递归链，适用于复杂逻辑拆分，提高可读性和模块化。
在实际开发中，应根据具体问题选择合适的递归方式，并注意设置好基准条件，避免栈溢出或无限递归。
如无特殊需要，优先使用迭代代替递归，以提升程序的健壮性。