エラーを意図的に投げるアレ。
Scalaで末尾再帰
再帰のあとに他の作業がはいっちゃダメなのが末尾再帰の根幹とのこと。
上が普通の再帰。下が末尾再帰。
具体的には、こういうこと。
n * factorial(n - 1)
こんなふうに、再帰のあとに計算が入る奴は末尾再帰じゃないよっていう話です。
再帰呼出しを往路と復路で考えると、末尾再帰は復路のない再帰呼出しと考えることが出来る。
往路で以下のような式を展開する。
(n * (n - 1 * (n - 2 * (n - 1 * (1)))))
で、復路で上の式を計算する。
再帰呼出しは、復路の計算を省くので、下のようになる。と思われる。
(5 * (4 * (3 * (2 * (1)))))
ちなみに、フィボナッチはこんな感じです。 なお、Scalaだと@annotation.tailrecというアノテーションがあって、このアノテーションをつけると、再帰が末尾再帰かどうかチェックしてくれたりする。
Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)
- 作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
- 出版社/メーカー: インプレス
- 発売日: 2015/03/20
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (2件) を見る
