js function 递归

递归（Recursion）是编程中的一个重要概念，特别是在JavaScript这样的函数式编程语言中。递归函数是指在函数的定义中直接或间接地调用自身的一种方法。递归通常用于解决可以分解为相似子问题的问题。

基础概念

递归函数通常包含两个主要部分：

1. 基本情况（Base Case）：这是递归结束的条件，防止函数无限调用自身，导致栈溢出错误。
2. 递归步骤（Recursive Step）：在这一步中，函数调用自身，通常会传递一个更小的参数或者更接近基本情况的参数。

优势

• 简洁性：递归可以使代码更加简洁和易于理解。
• 问题分解：递归适合解决那些可以自然分解为相似子问题的问题。

类型

• 直接递归：函数直接调用自身。
• 间接递归：函数通过其他函数间接调用自身。

应用场景

• 树形结构遍历：如文件系统遍历、DOM树遍历等。
• 排序算法：如快速排序、归并排序等。
• 搜索算法：如深度优先搜索（DFS）等。
• 动态规划问题：如斐波那契数列、汉诺塔问题等。

示例代码

以下是一个计算阶乘的递归函数示例：

function factorial(n) {
    // 基本情况
    if (n === 0 || n === 1) {
        return 1;
    }
    // 递归步骤
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 输出: 120

遇到的问题及解决方法

栈溢出错误：当递归调用层数过深时，可能会导致栈溢出错误。解决方法是：

1. 优化递归：通过尾递归优化或转换为迭代算法来减少调用栈的深度。
2. 增加栈大小：在某些环境中可以尝试增加调用栈的大小，但这通常不是最佳解决方案。

重复计算：在某些递归算法中，可能会重复计算相同的子问题。解决方法是使用记忆化（Memoization）技术来存储已经计算过的结果，避免重复计算。

示例代码：记忆化递归

function memoize(fn) {
    const cache = new Map();
    return function (...args) {
        if (cache.has(args.toString())) {
            return cache.get(args.toString());
        }
        const result = fn.apply(this, args);
        cache.set(args.toString(), result);
        return result;
    };
}

const fibonacci = memoize(function(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
});

console.log(fibonacci(10)); // 输出: 55

在这个示例中，memoize 函数用于缓存 fibonacci 函数的计算结果，从而避免了重复计算，提高了效率。