🧠 尾递归

🎯 什么是递归？

🏠 生活中的递归例子

俄罗斯套娃：每个套娃里面都有一个更小的套娃，直到最小的那个。

💡 编程中的递归

递归就是函数调用自己！就像俄罗斯套娃一样，函数里面又调用自己。

// 计算阶乘的例子
function factorial(n) {
    if (n === 1) {
        return 1;  // 基础情况：最小的套娃
    }
    return n * factorial(n - 1);  // 递归调用：打开下一个套娃
}

⚠️ 普通递归的问题

🚨 栈溢出问题

想象你在桌子上叠盘子，每调用一次函数就放一个盘子。如果叠得太高，桌子就撑不住了！

📊 普通递归的栈使用情况

// 普通递归 - 会占用大量栈空间
function factorial(n) {
    if (n === 1) return 1;
    return n * factorial(n - 1);  // 这里需要等待递归结果
}

// 调用 factorial(5) 时：
// factorial(5) 等待 factorial(4)
// factorial(4) 等待 factorial(3)
// factorial(3) 等待 factorial(2)
// factorial(2) 等待 factorial(1)
// factorial(1) 返回 1
// 然后一层层返回...

✨ 尾递归 - 聪明的解决方案

🎪 马戏团的杂技演员

想象一个杂技演员在表演：他不需要记住之前所有的动作，只需要知道当前这一步和下一步要做什么！

🎯 尾递归的特点

  • ✅ 递归调用是函数的最后一个操作
  • ✅ 不需要等待递归结果
  • ✅ 可以优化为循环，节省栈空间

📊 尾递归的栈使用情况

// 尾递归版本 - 栈空间使用很少
function factorialTail(n, accumulator = 1) {
    if (n === 1) {
        return accumulator;  // 直接返回结果
    }
    return factorialTail(n - 1, n * accumulator);  // 尾递归调用
}

// 调用 factorialTail(5) 时：
// factorialTail(5, 1) → factorialTail(4, 5)
// factorialTail(4, 5) → factorialTail(3, 20)
// factorialTail(3, 20) → factorialTail(2, 60)
// factorialTail(2, 60) → factorialTail(1, 120)
// factorialTail(1, 120) → 返回 120

📊 普通递归 vs 尾递归

特性 普通递归 尾递归
栈空间使用 ❌ 大量栈空间 ✅ 少量栈空间
性能 ❌ 可能栈溢出 ✅ 可优化为循环
递归位置 ❌ 递归后还有操作 ✅ 递归是最后操作
理解难度 😊 相对简单 🤔 需要思考

🎮 演示

点击按钮开始计算...

🎓 学习总结

🎯 关键要点

  1. 尾递归是递归调用的最后一个操作
  2. 尾递归可以优化为循环，节省内存
  3. 使用累加器参数来传递中间结果
  4. 尾递归是函数式编程的重要概念