末尾再起に関する理解

前提知識と言葉の定義

プログラムで関数が呼び出されると、OSはコールスタック領域に、パラメータや実行終了後に戻るべきコード内の場所など、関数に関する情報を格納する。
コールスタックとは、プログラム内で行われた関数呼び出しを追跡するために使用されるデータ構造のこと。
このコールスタックは、スタックと呼ばれる構造によって管理されているらしい。スタックは要素が入ってきた順に一列に並べ、後に入れた要素から順に取り出すという規則に従った構造で、2 つの操作 push、pop を行える。

• push：*情報をスタックに積む。
• pop：*情報をスタックから取り出す。
  ここでいう *情報は冒頭の文にあるように「パラメータや実行終了後に戻るべきコード内の場所など、関数に関する」情報のこと。だけど、今回はイメージしやすいように「関数そのもの」と捉えた方が良さそう。

本題：末尾再起

例えば、以下のような関数を定義する（1~nまでの数の総和を計算して値を返してくれる関数）。

function simpleSummation(n) {
  if(n <= 0) return 0;

  return simpleSummation(n-1) + n;
}
// 引数に5をいれて実行するとき、15が返り値として渡されるまでに実際には以下のような処理が行われている。
simpleSummation(5)
simpleSummation(4) + 5
(simpleSummation(3) + 4) + 5
((simpleSummation(2) + 3) + 4) + 5
(((simpleSummation(1) + 2) + 3) + 4) + 5
(((simpleSummation(0) + 1) + 2) + 3) + 4) + 5
((((0 + 1) + 2) + 3) + 4) + 5
(((1 + 2) + 3) + 4) + 5
((3 + 3) + 4) + 5
(6 + 4) + 5
10 + 5
15

この時、simpleSummation(0)がよばれた段階でスタックにはsimpleSummation(0)からsimpleSummation(5)までの計6つスタックがたまっている。

一般化すると、simpleSummation(n)を実行する時、n+1個の関数が順にスタックにpushされる。メモリには物理制限があるので、nがとても大きな値になるとスタックの保存上限を超えて、スタックオーバーフロー(スタックが溢れ出る)が発生する可能性がある。
こんな時、末尾再起によってスタックオーバーフローを回避できる場合があるそう。

以下のように、"return 再帰関数()" の形、つまりほかのすべての処理の最後で再起処理が行われるものを末尾再起という。(再帰関数とは、自分自身を呼び出す処理が書かれている関数のこと。一応補足)

function exFunc() {
  // 諸々の処理

  return exFunc();
}

1~nまでの数の総和を返してくれる関数を末尾再帰的な関数に書き換える。

function simpleSummationTail(n){
    return simpleSummationTailHelper(n, 0);
}

// 補助関数
function simpleSummationTailHelper(count, total){
    if(count <= 0 ) {
        return total;
    }

    return simpleSummationTailHelper(count-1, total+count);
}

末尾再帰では、計算の途中結果を保存する必要があるため、蓄積値を表す引数を追加する必要がある。その為、補助関数を使って元の関数に引数を追加して、補助関数で再帰処理を実行する。
引数に5をいれて実行すると、15が返り値として渡されるまでに実際には以下のような処理が行われる。

simpleSummationTail(5)
simpleSummationTailHelper(5,0)
simpleSummationTailHelper(4,5)
simpleSummationTailHelper(3,9)
simpleSummationTailHelper(2,12)
simpleSummationTailHelper(1,14)
simpleSummationTailHelper(0,15)
15

どちらにせよ、スタック積まれてない？って感じなのだけれど、"末尾呼び出し最適化"という末尾再起がスタックを消費しないように最適化されたコンパイル技術があるらしいらしく、これによりスタックが積み上がることを回避できる。

末尾呼び出し最適化
再帰関数が呼び出された時、新しいスタックフレーム（スタックデータごとのかたまり）を確保するのではなく、既存のスタックフレームの値が更新される。simpleSummationTail で例えると、simpleSummationTail が呼ばれた時、呼び出された関数が新しいスタックフレームに push されるのではなく、既存のスタックフレームの count と total が新しい値に更新される。結果スタックには、データが1つしか積み上がらないので、メモリを圧迫しないとのこと。

コメント

間違っている箇所ありましたら、コメントお願いします。