読者です 読者をやめる 読者になる 読者になる

微妙にあきらめてた人のための再帰入門2

2です。明日とかいっときながらだいぶ遅れました。
えーと、再帰には二種類の再帰があります。同じ再帰手続きでも再帰的プロセス反復的プロセスがあります。で、この反復的プロセスを表現するには末尾再帰がつかわれます。で、この末尾再帰で表現できることと、ループで表現できることはほぼ同等だったはずです。まとめると

表現力: 再帰(ふつうの)>>>> 再帰(末尾再帰)== ループ

とこんなかんじ、 再帰(ふつうの)でしか表現できない構造っていうのはクイックソートとかのスタックの操作が必要になるものです。ループでも自力でスタックを使えば実現できなくもないんですが、基本的に再帰の方がスマート。
http://www.drk7.jp/MT/archives/000995.html
詳しくはこことか参照

で、実例。前回書いたこのフィボナッチ

def fib n
  if n == 0
    0
  elsif n == 1
    1
  else
    fib(n-1) + fib(n-2)
  end
end

末尾再帰を使うとこんな風に書き直せます。

def fib n
  def fib_iter a, b, count
    if count == 0
      b
    else
      fib_iter a+b, a, count-1
    end
  end
  
  fib_iter 1, 0, n
end

これだとfib_iterが自分自身を呼んだ時の戻り値が、fib_iter自身の戻り値となるので、上のやつみたいに関数スタックにガシガシ積む必要がなくなり、末尾再帰の最適化をやってくれる処理系ならば、再帰呼び出しはただのジャンプになります。つまりループと同じ。この末尾再帰の最適化はスピードを重視する処理系ならたいていやってくれます。
関数型言語の処理系ならほぼ100%やってくれます。Cは無理かとおもってたけど、「gccはちゃんとやってくれるよ」って id:daiki41ti がいってた。

まとめると、
スピード: 再帰(末尾再帰)== ループ >>>> 再帰(ふつうの)
メモリ使用量: 再帰(末尾再帰)== ループ >>>>>>>> 再帰(ふつうの)
こんなかんじ


で、これならループを使えばいいじゃんっておもう人がいるとおもいます。それでいいとおもいます。