递归算法深度解析：从斐波那契到汉诺塔

什么是递归

递归是一种编程技术，函数直接或间接地调用自身来解决问题。递归算法通常将复杂问题分解为更小的相同类型的子问题，直到达到基本情况为止。

递归的基本要素

一个有效的递归算法必须包含两个关键要素：基本情况和递归情况。基本情况是递归的终止条件，递归情况是将问题分解为更小的子问题。

斐波那契数列

斐波那契数列是最经典的递归问题之一，每个数字都是前两个数字的和。

function fibonacci(n) {
    // 基本情况
    if (n <= 1) {
        return n;
    }
    
    // 递归情况
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 使用示例
console.log(fibonacci(10)); // 输出: 55

优化版本（记忆化）

原始递归版本存在大量重复计算，可以通过记忆化技术优化。

function fibonacciMemo(n, memo = {}) {
    if (n in memo) {
        return memo[n];
    }
    
    if (n <= 1) {
        return n;
    }
    
    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

汉诺塔问题

汉诺塔是一个经典的递归问题，展示了递归在解决复杂问题时的优雅性。

function hanoi(n, source, destination, auxiliary) {
    if (n === 1) {
        // 基本情况：只有一个盘子
        console.log(`移动盘子从 ${source} 到 ${destination}`);
        return;
    }
    
    // 递归步骤1：将n-1个盘子从源柱移动到辅助柱
    hanoi(n - 1, source, auxiliary, destination);
    
    // 递归步骤2：将最大的盘子从源柱移动到目标柱
    console.log(`移动盘子从 ${source} 到 ${destination}`);
    
    // 递归步骤3：将n-1个盘子从辅助柱移动到目标柱
    hanoi(n - 1, auxiliary, destination, source);
}

// 使用示例
hanoi(3, 'A', 'C', 'B');

递归与迭代的对比

递归的应用场景

• 树和图的遍历
• 分治算法（如快速排序、归并排序）
• 动态规划问题
• 数学计算（阶乘、幂运算）
• 文件系统遍历

二叉树的递归遍历

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 前序遍历
function preorderTraversal(root) {
    if (!root) return [];
    
    const result = [root.val];
    result.push(...preorderTraversal(root.left));
    result.push(...preorderTraversal(root.right));
    
    return result;
}

// 中序遍历
function inorderTraversal(root) {
    if (!root) return [];
    
    const result = [];
    result.push(...inorderTraversal(root.left));
    result.push(root.val);
    result.push(...inorderTraversal(root.right));
    
    return result;
}

// 后序遍历
function postorderTraversal(root) {
    if (!root) return [];
    
    const result = [];
    result.push(...postorderTraversal(root.left));
    result.push(...postorderTraversal(root.right));
    result.push(root.val);
    
    return result;
}

递归陷阱与注意事项

• 栈溢出：递归深度过大会导致调用栈溢出
• 重复计算：相同子问题被多次计算，效率低下
• 无限递归：缺少正确的终止条件
• 内存消耗：每次递归调用都会占用栈空间

尾递归优化

尾递归是一种特殊的递归形式，递归调用是函数的最后一个操作。某些语言和编译器可以优化尾递归，将其转换为迭代形式。

// 非尾递归版本
function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1); // 递归调用后还有乘法运算
}

// 尾递归版本
function factorialTail(n, acc = 1) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc); // 递归调用是最后一步
}

总结

递归是解决许多编程问题的强大工具，它能够以简洁优雅的方式表达复杂的逻辑。理解递归的基本原理和常见模式，掌握递归与迭代的转换技巧，是每个程序员必备的技能。

在实际应用中，要根据问题的特点和性能要求，合理选择递归或迭代的实现方式。对于可以自然递归建模的问题，递归通常能提供更好的代码可读性和维护性。