末尾再帰：Tail Recursion

Scalaを勉強している中で「末尾再帰」という概念を知りました。

ここでは「末尾再帰」について記載します。

末尾再帰とは

「末尾再帰」とは再帰の一種です。

一番最後に自分自身を呼び出して、後は値を返すだけで、その後になにもやることが残っていない再帰のことを指します。

参考サイト：http://karetta.jp/book-node/gauche-hacks/004664

具体例

not末尾再帰関数

◆コード

def fuctorial(n: Int): Int = 
  if (n == 1) 1 else n * factorial(n - 1)

◆実行例

fuctorial(3)
-> if(3 == 1) 1 else 3 * factorial(3 - 1)
-> 3 * factorial(2)
-> 3 * 2 * factorial(1)
-> 3 * 2 * 1
-> 6

末尾再帰関数

◆コード

def fuctorial(n: Int): Int = {
  def loop(acc: Int, n: Int): Int = 
    if(n == 1) acc else loop(acc * n, n - 1)
  loop(1, n)
  }
}

◆実行例

fuctorial(3)
-> loop(1, 3)
-> if(3 == 1) 1 else loop(1 * 3, 3 - 1)
-> loop(3, 2)
-> if(2 == 1) 3 else loop(3 * 2, 2 - 1)
-> loop(6, 1)
-> if(1 == 1) 6 else loop(6 * 1, 1 - 1)
-> 6

メリット

末尾再帰では末尾最適化が適用され処理効率が向上するようです。

詳細はWikipediaの末尾再帰に記載されている「末尾最適化」を参照ください。

tailrecアノテーション

Scalaでは関数に「tailrecアノテーション」を付けることで末尾再帰になっていない再帰を検知し、コンパイルエラーにすることができるようです。

参考サイト：http://www.ne.jp/asahi/hishidama/home/tech/scala/annotation/tailrec.html

tailrecアノテーションは下記のようなに記載します。

@tailrec
def fuctorial(n: Int): Int = 
  if (n == 1) 1 else n * factorial(n - 1)

この場合末尾再帰になっていないので、コンパイルエラーになりますね。