递归 vs 迭代 —— 原理与效率对比

通过交互式可视化学习递归与迭代的执行流程、理解递归的核心思想，并直观对比它们的性能差异。

核心概念速览

递归：自己调用自己

解决思想： 将一个大问题分解为结构相同、规模更小的子问题来求解。
基准情况 (Base Case): 必须有一个或多个明确的、可以直接求解的最小问题，作为递归的出口，防止无限调用。
递归步骤 (Recursive Step): 在这一步中，函数调用自身来处理规模减小的子问题。
结果合并： 子问题解决后，可能需要将结果组合起来得到原问题的解。

迭代：循环重复执行

解决思想： 使用循环结构（如 for, while）反复执行一段代码，逐步逼近最终结果。
状态更新： 每次循环通常会更新一个或多个变量的状态。
终止条件： 循环必须有明确的结束条件，否则会无限循环。
直接计算： 通常直接计算结果，不涉及函数调用栈的开销。

递归 vs 迭代

递归优点： 代码可能更简洁、易懂，尤其适合处理具有天然递归结构的问题（如树）。
递归缺点： 函数调用有开销，可能占用较多栈空间，深度过大可能导致栈溢出，效率通常低于迭代。
迭代优点： 效率高，内存占用固定（通常），不易栈溢出。
迭代缺点： 对于复杂递归逻辑，代码可能不如递归直观。

选择算法: 输入 n:

速度:

递归实现

请选择算法和 n，然后点击“开始对比”

迭代实现

请选择算法和 n，然后点击“开始对比”

效率对比

递归调用次数 / 步骤

迭代循环次数 / 步骤

最大栈深度 (递归)

空间复杂度 (迭代)

O(1)

相对执行时间估算递归 : 迭代 = 1 : 1

递归

迭代

注意：时间估算基于操作步骤数，并非实际执行时间。递归的函数调用开销未完全计入。

算法实现代码 (C++)

阶乘 (Factorial)

斐波那契 (Fibonacci)

阶乘 (Factorial)

// --- 阶乘的递归实现 ---
long long factorial_recursive(int n) {
    // 1. 基准情况 (Base Case): n=0 或 n=1 时，阶乘为 1
    if (n <= 1) {
        return 1;
    }
    // 2. 递归步骤 (Recursive Step): n! = n * (n-1)!
    //    调用自身解决规模更小的子问题 factorial_recursive(n - 1)
    long long sub_result = factorial_recursive(n - 1);

    // 3. 结果合并: 将子问题的解与当前步骤结合
    return n * sub_result;
}

// --- 阶乘的迭代实现 ---
long long factorial_iterative(int n) {
    if (n < 0) { return -1; } // 负数阶乘无定义 (或者抛出异常)
    if (n <= 1) { return 1; } // 0! = 1, 1! = 1

    long long result = 1; // 初始化结果

    // 循环计算: 从 2 乘到 n
    for (int i = 2; i <= n; ++i) {
        result *= i; // 状态更新：累乘
    }
    // 循环结束条件: i > n

    return result; // 返回最终计算结果
}

斐波那契数列 (Fibonacci)

注意：递归斐波那契效率极低，因为存在大量重复计算。

// --- 斐波那契的递归实现 (效率较低) ---
int fibonacci_recursive(int n) {
    // 1. 基准情况 (Base Cases): Fib(0)=0, Fib(1)=1
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }

    // 2. 递归步骤 & 3. 结果合并: Fib(n) = Fib(n-1) + Fib(n-2)
    //    直接在 return 语句中进行了两次递归调用和结果合并
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

// --- 斐波那契的迭代实现 (效率高) ---
int fibonacci_iterative(int n) {
    if (n <= 0) { return 0; }
    if (n == 1) { return 1; }

    int a = 0; // 代表 Fib(i-2)
    int b = 1; // 代表 Fib(i-1)
    int current_fib = 0; // 用于存储 Fib(i)

    // 循环计算: 从 i=2 开始计算到 n
    for (int i = 2; i <= n; ++i) {
        // 计算当前斐波那契数
        current_fib = a + b;

        // 更新状态，为下一次循环准备
        a = b;       // 下一轮的 Fib(i-2) 是当前的 Fib(i-1)
        b = current_fib; // 下一轮的 Fib(i-1) 是当前的 Fib(i)
    }
    // 循环结束条件: i > n

    return current_fib; // 返回 Fib(n)
}