时间戳

首页 > 解决方案 > 为什么我的递归函数会导致：超出最大调用堆栈大小？

javascript - 为什么我的递归函数会导致：超出最大调用堆栈大小？

问题描述

问题

这个问题的名字可以说是古代历史学家约瑟夫斯一生中最重要的事件：根据他的故事，他和他的 40 名士兵在一次围攻中被罗马人困在一个山洞里。

他们拒绝向敌人投降，而是选择了集​​体自杀，但有一个转折：他们围成一圈，每三个人就杀死一个人，直到剩下最后一个人（并且应该自杀以结束这一行为） ）。

好吧，约瑟夫斯和另一个人是最后两个，而且，正如我们现在知道故事的每一个细节，你可能已经正确地猜到了他们并没有完全遵循最初的想法。

您现在要创建一个返回 Josephus 排列的函数，将要排列的项目的初始数组/列表作为参数，就好像它们在一个圆圈中一样，并计算每 k 个位置，直到没有剩余。

提示和注意事项：从 1 到 n 开始计数会有所帮助，而不是通常的范围 0..n-1；k 将始终 >=1。

例如，当 n=7 和 k=3 时，josephus(7,3) 应该这样做。

[1,2,3,4,5,6,7] - initial sequence
[1,2,4,5,6,7] => 3 is counted out and goes into the result [3]
[1,2,4,5,7] => 6 is counted out and goes into the result [3,6]
[1,4,5,7] => 2 is counted out and goes into the result [3,6,2]
[1,4,5] => 7 is counted out and goes into the result [3,6,2,7]
[1,4] => 5 is counted out and goes into the result [3,6,2,7,5]
[4] => 1 is counted out and goes into the result [3,6,2,7,5,1]
[] => 4 is counted out and goes into the result [3,6,2,7,5,1,4]
So our final result is:

josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4]

这是我的解决方案

function josephus(items, k, a = [1]){
  let newArr = [];

  //when there is no array items left return the array 
  if(items.length == 1){
    newArr.push(items[0]);
    return newArr;
  }
  // recursive loop that keeps firing
  if((a[0] + k) > items.length){


    let surplus = items.length - (a[0] + k);
   a[0] = surplus;
    newArr.push(items[surplus]);
    
  } else {
    newArr.push(items[k + a[0]]);
    a[0] = items.indexOf((k + a[0]));

  }
 
  return josephus(items, k, a);
  
}


console.log(josephus([1,2,3,4,5,6,7,8,9,10],1));
console.log(josephus([1,2,3,4,5,6,7,8,9,10],2));
console.log((josephus(["C","o","d","e","W","a","r","s"],4)));

还有一个问题

如果我的解决方案是固定的，那么只要要跳过的人数低于总人数 x2 ，它就会循环。但是如果我们需要跳过让我们说六个人，但总共只有 2 人，它就会中断。因此我们需要解决这个问题。我相信这样做的方法是在递归函数内部构建一个递归函数。您将如何创建内部递归函数？

注意：我代码中的 j 是为了阻止浏览器崩溃。

标签： javascriptalgorithmrecursion

解决方案

当您在调试器中运行程序时，您会注意到该行return josephus(items, k, a);始终使用相同的items数组执行。递归的终止条件是数组的长度变为 1，但如果您不从函数中的数组中删除任何元素，则不会发生这种情况。

推荐阅读