递归实现自定义步长爬楼梯报错：无法读取undefined的length属性求修正

嗨，这个问题其实很好排查——你在递归调用的时候漏掉了传递步长数组arr参数！

错误原因分析 #

当你在循环里执行add(x-arr[i])时，只传入了剩余步数x-arr[i]，却没把允许步长数组arr传下去。这样进入下一层递归函数时，arr参数就变成了undefined，当代码尝试访问arr.length时，自然就抛出了cannot read property 'length' of undefined的错误。

修正后的基础版本 #

只需要在递归调用时补上arr参数就行：

function add(x, arr) { 
  let result = 0 
  if(x < 0) return 0; 
  if(x === 0) return 1; 
  else{
    for(let i = 0 ; i < arr.length ; i++){ 
      // 关键：递归调用时必须传递arr参数
      result += add(x - arr[i], arr); 
    } 
    return result
  }; 
} 
console.log(add(4, [1,3])); // 输出3，和预期一致

优化建议：加入记忆化缓存 #

不过纯递归的写法会有大量重复计算（比如计算add(4, [1,3])时，会多次重复计算add(1, [1,3])这类子问题），当总步数x很大时，效率会很低。我们可以加入记忆化缓存来优化，把已经计算过的子问题结果存起来，避免重复计算：

// 带记忆化的优化版本
function add(x, arr, memo = {}) { 
  // 如果当前x的结果已经缓存过，直接返回
  if (memo[x] !== undefined) return memo[x];
  
  let result = 0 
  if(x < 0) return 0; 
  if(x === 0) return 1; 
  else{
    for(let i = 0 ; i < arr.length ; i++){ 
      result += add(x - arr[i], arr, memo); 
    } 
    // 将当前x的结果存入缓存
    memo[x] = result;
    return result
  }; 
} 
console.log(add(4, [1,3])); // 输出3

这个优化版本的时间复杂度从纯递归的O(k^n)（k是步长数组长度，n是总步数）降到了O(n*k)，性能提升非常显著。

内容的提问来源于stack exchange，提问作者Aditya Singh