🔖

tail recursion: 末尾再帰について

2024/04/09に公開

JavaScript

はじめに

ほとんど自分のメモ書きみたいな感じなので、詳しい解説は、参考にしたpebblipさんのこちらのサイトをご参照ください。

tail recursion とは

tail recursion (末尾再帰) とは、再帰関数において、自身の再帰呼び出しがその関数におけるリターン前の最後の処理である再帰のことを言う。また一般的に、そのようなリターン前の最後の呼び出しを、末尾呼び出しと呼ぶ。

下のコードを例にとると、一つ目のコードは、リターン前の最後の処理がFactorial関数の呼び出しであるため tail recursion であるが、二つ目のコードは、xとFactorial関数の呼び出し結果の掛け算の計算処理が最後の処理となるため、tail recursion ではない。

// tail recursion
function Factorial(x, total = 1) {
  if (x === 0) {
    return total
  } else {
    return Factorial(x-1, total * x)
  }
}

// normal recursion
function Factorial(x) {
  if (x <= 1) {
    return 1;
  } else {
    return x * Factorial(x - 1);
  }
}

tail recursion の何が嬉しいか

tail recursionを使う利点としては、スタックオーバーフローを避けられる場合があることである。
例えば、x = 4として、先ほどの通常の再帰のコードを実行した時のことを考える。

// normal recursion
Factorial(4);
4 * Factorial(3);
4 * (3 * Factorial(2));
4 * (3 * (2 * Factorial(1)));
4 * (3 * (2 * 1));

-> 24

このように通常の再帰では、計算途中の値が保持されたまま(スタックフレームに保持される)処理が進むため、再帰呼び出しの階層が深くなりすぎると、メモリがかなり消費されてしまい、スタックオーバーフローを引き起こす可能性もある。これはできるならば避けたい。

しかし、tail recursionを使用した場合、x = 4として実行した場合、以下のようになる。

// tail recursion
Factorial(4);
Factorial(4, 1);
Factorial(3, 4);
Factorial(2, 12);
Factorial(1, 24);
Factorial(0, 24);

-> 24

この場合、Factorial(4)の返り値はFactorial(4, 1)の結果、Factorial(4, 1)の返り値はFactorial(3, 4)の結果、・・・、Factorial(1, 24)の返り値はFactorial(0, 24)の結果となるように、全ての関数の返り値は全て同じ値であり、先ほどと異なり保持すべき計算途中の値がないため、新たにスタックフレームを用意する必要がない。

そのため、Factorial(4)のスタックフレームをFactorial(4, 1)のスタックフレームとして再利用する、Factorial(4, 1)のスタックフレームをFactorial(3, 4)のスタックフレームとして再利用するという動作を繰り返せば、使用するスタックフレームは一つで済み、メモリの無駄を省くことができる。

補足:
このような再利用の操作を末尾呼び出しの除去(tail call elimination) と呼び、コンパイラや実行環境が行う末尾呼び出しの除去を末尾呼び出し最適化(tail call optimization) と呼ぶ。

注意点

末尾呼び出し最適化が行われるかは言語や実行環境に依存しており、末尾再帰のコードを記述したとしても、末尾最適化が必ず行われるとは限らないため、その点に注意が必要。

はじめに

tail recursion とは

tail recursion の何が嬉しいか

注意点

Discussion