JavaScript、再帰関数に関しまして

Question

お世話になっております。
Codewars、というサイトを使ってJavaScriptを学習中のものです。
[50, 55, 56, 57, 58]のような数字をその要素とするリストからk個選び、その合計がt以下になる組み合わせのうち、合計値が最大のものを求めよ、という課題がありました。

function chooseBestSum(t, k, ls) {
  var biggestCount = 0;
  var recurseTowns = function(townsSoFar, lastIndex) {
//    console.log(townsSoFar)
    townsSoFar = townsSoFar || [];
    //base case
    if (townsSoFar.length === k) {
      var sumDistance = townsSoFar.reduce((a,b)=>a+b);
      if (sumDistance <= t && sumDistance > biggestCount) {
        biggestCount = sumDistance;
      }
      return; //EJECT
    }
    //recursive case
    for (var i = lastIndex + 1 || 0; i < ls.length; i++) {
      recurseTowns(townsSoFar.concat(ls[i]), i);
    }
  }
  recurseTowns();

  return biggestCount || null;
}
var ls = [50, 55, 56, 57, 58];
console.log(chooseBestSum(163, 3, ls))//163

この関数を実行すると、
recurseTowns([50],0)
recurseTowns([50,55],1)
recurseTowns([50,55,56],2)
のようにスタックが増えていき、
まずrecurseTowns([50,55,56],2)がreturnを実行すると思います。
このあと
recurseTowns([50,55],1)に移ると思うのですが、

for (var i = lastIndex + 1 || 0; i < ls.length; i++) {
recurseTowns(townsSoFar.concat(ls[i]), i);
}
ここで"i = lastIndex + 1"となっているため、i = 2 となってしまい、またrecurseTowns([50,55,56],2)がまた実行されてしまうのでは、と考えてしまいます。

まずrecurseTowns([50,55,56],2)がreturnを実行した後の挙動はどのようなものになるのでしょうか？

よろしくお願いいたします。

Comments

[kei344]

まだ質問が「受付中」になっていますが、「ベストアンサー」を選び「解決済」にされてはいかがでしょうか。

[Behemoth]

返信が遅くなりました。ご指摘、ありがとうございます!

Answer 1

まずrecurseTowns([50,55,56],2)がreturnを実行した後の挙動はどのようなものになるのでしょうか？

再帰関数を考える上での定石は、「たまたま同じ名前の関数を呼び出しているだけ」と考えることです。言語によってはstaticなど、再帰していても変わらないものもありますが、JavaScriptでは、関数の引数や関数内で宣言された変数は、実行ごとにバラバラです。

呼び出されたrecurseTownsの中でvar i = (何か);が実行されていますが、それは呼び出した側のiには全く無関係です。

そういう目でループを見てみれば、recurseTowns([50,55,56],2)を実行して戻ってきたあとは、forループでi++されて、次のrecurseTowns([50,55,57],2)を生成するように進んでいきます。

Comments

[Behemoth]

ご返信が遅れて申し訳ありません。
「たまたま同じ名前の関数を呼び出しているだけ」
このご説明で納得できました。
ご解説、ありがとうございます。
またよろしくお願いいたします。