KDOC 599: 関数の最後の操作が再帰呼び出しの結果をそのまま返すだけならスタックフレームを破棄できる

この文書のステータス

  • 作成
    • <署名>
  • レビュー
    • <署名>

概要

関数の最後の操作が再帰呼び出しの結果をそのまま返すだけなら、スタックフレームを破棄できる。呼び出し元に戻ってやる計算がないので、呼び出し元のフレームを保持する必要はない。

末尾再帰にするためにアキュムレータを使う。 

function sum(nums: readonly number[], acc=0): number {
  if (nums.length === 0) {
    return acc;
  }
  return sum(nums.slice(1), nums[0] + acc);
}

逆にアキュムレータを使わず末尾再帰でないバージョン。リストに含まれる要素の数だけ、再帰呼び出しによりメモリのスタック領域が使われる。再帰呼び出しから戻ったあとに加算する必要があるので各フレームを保持し続ける必要がある。

  • 1 + (2 + (3 + (... + 0)))
function sum(nums: readonly number[]): number {
  if (nums.length === 0) {
    return 0;
  }
  return nums[0] + sum(nums.slice(1));
}

関連