面试题：JavaScript递归函数在函数式编程中的应用及优化

Question

在函数式编程范式下，使用JavaScript递归函数实现一个 `reduce` 类似的功能，对数组中的每个元素执行累加操作。要求能够处理嵌套数组（即数组中的元素可能也是数组），并且实现一个记忆化（Memoization）版本来优化递归性能。解释记忆化是如何提升性能以及在这种场景下的适用范围。

Answer 1

实现带有记忆化的递归 reduce 类似功能

// 记忆化缓存
const memoize = (fn) => {
    const cache = new Map();
    return (arg) => {
        const key = arg.toString();
        if (cache.has(key)) {
            return cache.get(key);
        }
        const result = fn(arg);
        cache.set(key, result);
        return result;
    };
};

// 递归处理嵌套数组并累加
const nestedReduce = (arr, initial = 0) => {
    let sum = initial;
    for (let i = 0; i < arr.length; i++) {
        if (Array.isArray(arr[i])) {
            sum += nestedReduce(arr[i]);
        } else {
            sum += arr[i];
        }
    }
    return sum;
};

// 记忆化版本
const memoizedNestedReduce = memoize(nestedReduce);

记忆化提升性能的原理

记忆化通过缓存函数的计算结果，避免了重复计算。当相同的输入再次出现时，直接从缓存中获取结果，而不需要重新执行函数体。在递归计算嵌套数组累加的场景中，如果存在重复的子数组，记忆化可以显著减少递归调用次数，从而提升性能。

记忆化在这种场景下的适用范围

1. 输入重复性高：如果嵌套数组中存在大量重复的子数组结构，记忆化能极大提升性能。例如，数组中多次出现相同的子数组片段。
2. 计算代价大：递归计算嵌套数组累加本身可能会因为多次重复遍历子数组而消耗较多资源，记忆化对于这种计算代价较大的操作优化效果明显。
3. 数据结构相对稳定：如果数组结构不会频繁变化，缓存的结果可以被多次复用，记忆化就很适用。但如果数组频繁变动，缓存的有效性会降低。