末尾再帰（最適化）について調べる

すごいE本の「再帰さん、こんにちは！」を読んでて、末尾再帰のところが理解できなかったので調べた。

基本的な再帰関数duplicate/2

以下は整数の第二引数の項を第一引数の数だけコピーしたリストを作る関数。(「すごいErlang ゆかいに学ぼう！」55頁より)

duplicate(0,_) ->
  [];
duplicate(N,Term) when N > 0 ->
  [Term|duplicate(N-1, Term)].

当然、第一引数の値が大きいとstack overflowになる。もしくは多くのメモリを消費する。これはいい。これを改善するために末尾再帰をやってみよう！というのが以下。

末尾再帰にしたduplicate/2

末尾再帰にするとこうなる。(書籍は関数名をtail_duplicateにしているけど、ここではduplicatenのままとする。)

duplicate(N,Term) ->
  duplicate(N,Term,[]).

duplicate(0,_,List) ->
  List;
  
duplicate(N,Term,List) when N > 0 ->
  duplicate(N-1, Term, [Term|List])].

ここで思ったのは、Listという一時変数（アキュムレータ)を渡すことで呼び出した関数の結果に依存することはなくなるんだろうけど、結局関数呼んでるわけだしスタック消費するじゃん！、と。これは「末尾呼び出しの最適化」なるものがかかっているらしく、こいつを頭に入れることでようやく理解できた。

この記事が分かりやすかった。

bleis-tift.hatenablog.com

末尾呼び出しというのは、関数を呼び出した後に結果を戻す以外にすることがないような関数呼び出しのことを言います

末尾呼び出しは「関数から戻ってきた後に結果を戻す以外にすることがないような関数呼び出し」でした。何もすることがないのなら、関数呼び出しじゃなくて、単なるジャンプ命令に置き換えてしまえばスタックを消費しなくなっていいよね！というのが末尾呼び出しの最適化です

なるほど。

と、ここまで書いて理解できたから先に行こうと読み進めたら、ちゃんと書いてあった。(「すごいErlang ゆかいに学ぼう！」59頁より)

なぜなら仮想マシンは、関数が自分自身を末尾(関数内で評価される最後の式）で呼び出していたら、現在のスタックフレームを削除するからです。

あと、このようにも書いてある。

a() -> b(). b() -> c(). c() -> a().のような関数の連鎖があるとします。これはLCO(終端呼び出し最適化)がスタックのオーバーフローを避けるので、メモリが枯渇しない無限ループを効率的に生成します。

JavaScriptでは？

どうなってるのか気になったので調べてみた。

teppeis.hatenablog.com

どうやら2015年になってからBabelに末尾再帰最適化が入ったらしい。試してみる。

function duplicate(n, term, list = []) {
  if (n === 0) return list;
  return duplicate(n - 1, term, list.unshift(term));
}

これをバベる。

"use strict";

function duplicate(_x2, _x3) {
  var _arguments = arguments;
  var _again = true;

  _function: while (_again) {
    var n = _x2,
        term = _x3;
    list = undefined;
    _again = false;
    var list = _arguments.length <= 2 || _arguments[2] === undefined ? [] : _arguments[2];

    if (n === 0) return list;
    _arguments = [_x2 = n - 1, _x3 = term, list.unshift(term)];
    _again = true;
    continue _function;
  }
}