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

by shigemk2

当面は技術的なことしか書かない

Scalaで末尾再帰

Scala

再帰は再帰なんかじゃない!末尾再帰こそが真の再帰なんだ!

再帰のあとに他の作業がはいっちゃダメなのが末尾再帰の根幹とのこと。

上が普通の再帰。下が末尾再帰。

具体的には、こういうこと。

n * factorial(n - 1)

こんなふうに、再帰のあとに計算が入る奴は末尾再帰じゃないよっていう話です。

gist.github.com

再帰呼出しを往路と復路で考えると、末尾再帰は復路のない再帰呼出しと考えることが出来る。

往路で以下のような式を展開する。

(n * (n - 1 * (n - 2 * (n - 1 * (1)))))

で、復路で上の式を計算する。

再帰呼出しは、復路の計算を省くので、下のようになる。と思われる。

(5 * (4 * (3 * (2 * (1)))))

d.hatena.ne.jp

ちなみに、フィボナッチはこんな感じです。 なお、Scalaだと@annotation.tailrecというアノテーションがあって、このアノテーションをつけると、再帰が末尾再帰かどうかチェックしてくれたりする。

gist.github.com

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)