递归调用

一、递归调用的概念

函数可以直接或者间接地调用自身，称为递归调用。递归是程序设计中一种重要的算法思想，适合解决具有自相似结构的问题。

直接递归

函数体内直接调用自身：

void fun()
{
    // ...
    fun();   // 调用自身
}Code language: JavaScript (javascript)

间接递归

函数 A 调用函数 B，函数 B 又调用函数 A（通过其他函数间接调用自身）：

void A();
void B();

void A()
{
    // ...
    B();   // A 调用 B
}

void B()
{
    // ...
    A();   // B 调用 A，间接递归
}Code language: JavaScript (javascript)

二、递归的两个必要条件

1. 递归终止条件：必须有一个明确的结束条件，使递归能够停止。
2. 递归递推关系：每次递归调用都应使问题规模缩小，逐步逼近终止条件。

缺少终止条件或问题规模不缩小，会导致无限递归，最终引发栈溢出。

三、示例：求 n 的阶乘

阶乘的数学定义：

• n! = n × (n-1) × (n-2) × … × 2 × 1
• 0! = 1

递归定义：

• 当 n = 0 时，n! = 1（终止条件）
• 当 n > 0 时，n! = n × (n-1)!（递推关系）

int fun(int n)
{
    if (n == 0)
    {
        return 1;          // 终止条件
    }
    else
    {
        return n * fun(n - 1);  // 递归调用，问题规模缩小
    }
}Code language: JavaScript (javascript)

调用 fun(5) 的执行过程：

调用层次	执行操作	返回值
fun(5)	5 * fun(4)	等待 fun(4)
fun(4)	4 * fun(3)	等待 fun(3)
fun(3)	3 * fun(2)	等待 fun(2)
fun(2)	2 * fun(1)	等待 fun(1)
fun(1)	1 * fun(0)	等待 fun(0)
fun(0)	return 1	1
fun(1)	1 * 1	1
fun(2)	2 * 1	2
fun(3)	3 * 2	6
fun(4)	4 * 6	24
fun(5)	5 * 24	120

最终输出 120。

四、代码示例

以下代码演示了递归调用的多种应用场景：

#include <iostream>
using namespace std;

// 示例1：阶乘（递归）
int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

// 示例2：斐波那契数列（递归）
int fibonacci(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

// 示例3：求最大公约数（欧几里得算法，递归）
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 示例4：计算 x 的 n 次方（递归）
int power(int x, int n)
{
    if (n == 0)
        return 1;
    else
        return x * power(x, n - 1);
}

// 示例5：字符串逆序输出（递归）
void reverseString(const char* str, int index)
{
    if (str[index] == '\0')
        return;
    reverseString(str, index + 1);
    cout << str[index];
}

// 示例6：求数组元素之和（递归）
int sumArray(int arr[], int size)
{
    if (size == 0)
        return 0;
    else
        return arr[size - 1] + sumArray(arr, size - 1);
}

// 示例7：汉诺塔问题（递归）
void hanoi(int n, char from, char to, char aux)
{
    if (n == 1)
    {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, aux, to, from);
}

// 示例8：求 1~n 之和（递归）
int sumToN(int n)
{
    if (n == 1)
        return 1;
    else
        return n + sumToN(n - 1);
}

int main()
{
    // 测试阶乘
    cout << "5! = " << factorial(5) << endl;

    // 测试斐波那契
    cout << "fibonacci(10) = " << fibonacci(10) << endl;

    // 测试最大公约数
    cout << "gcd(48, 18) = " << gcd(48, 18) << endl;

    // 测试幂运算
    cout << "2^10 = " << power(2, 10) << endl;

    // 测试字符串逆序
    cout << "Reverse: ";
    reverseString("Hello", 0);
    cout << endl;

    // 测试数组求和
    int arr[] = { 1, 2, 3, 4, 5 };
    cout << "Sum of array = " << sumArray(arr, 5) << endl;

    // 测试 1~n 之和
    cout << "Sum 1~100 = " << sumToN(100) << endl;

    // 测试汉诺塔（3 层）
    cout << "\nHanoi Tower (3 disks):" << endl;
    hanoi(3, 'A', 'C', 'B');

    return 0;
}Code language: PHP (php)

五、递归与循环的对比

特性	递归	循环
思路	将大问题分解为同类小问题	重复执行某段代码
终止	终止条件 + return	循环条件变为 false
内存	每次调用占用栈空间，可能栈溢出	只使用当前变量，内存效率高
可读性	对递归问题（如树、分治）更直观	对简单重复操作更直观
性能	函数调用有开销，可能重复计算	效率高，无调用开销

同一个问题往往既可以用递归也可以用循环解决。选择依据：问题是否天然具有递归结构、代码可读性要求、性能要求。

六、注意事项

• 递归必须有明确的终止条件，且每次递归调用都应使问题规模缩小，否则会导致无限递归和栈溢出。
• 递归调用有函数调用开销，对于深度较大的递归（如斐波那契数列的朴素递归），效率较低。可以考虑用循环或记忆化优化。
• 递归适合解决分治、树遍历、回溯等具有自相似结构的问题。
• 间接递归中，两个函数都必须有终止条件，否则同样导致无限递归。
• 调试递归程序时，可以在函数入口和出口打印信息，观察调用层次和返回值。

七、常见错误

1. 缺少终止条件

int fun(int n)
{
    return n * fun(n - 1);   // 没有终止条件，无限递归
}Code language: JavaScript (javascript)

2. 终止条件不可达

int fun(int n)
{
    if (n == 1)
        return 1;
    return fun(n);   // 问题规模没有缩小，永远到不了 n==1
}Code language: JavaScript (javascript)

3. 递归深度过大

int fib(int n)
{
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);   // n 稍大（如 50）就极慢
}Code language: JavaScript (javascript)

对于斐波那契数列，应使用循环或记忆化递归。