こんにちは、ピーターです。

「Scala関数型デザイン&プログラミング」という関数型プログラミングの入門書を読み始めまして、その中に練習問題がたくさん出てくるのですが、その最初の練習問題について書こうと思います。

その問題はこちらです。

n番目のフィボナッチ数を取得する再帰関数を記述せよ。
最初の２つのフィボナッチ数は0と1である。
n番目の数字は常に前の2つの数字の合計となる。
この数列は0, 1, 1, 2, 3, 5のように始まる。
再帰関数の定義では、ローカルな末尾再帰関数を使用すること。

「ローカルな」というのは、関数の中に関数を定義するということです。
末尾再帰というのは、呼び出し元が再帰呼び出しした結果の値を返す以外にはもう何もしないということです。例えば、再帰呼び出しした結果の値に+1して返すと末尾再帰ではなくなります。

そして僕が考えたコードはこちらです。

def fib(n: Int): Int = {

  def loop(a: Int, b: Int, i:Int): Int = {
    if (n == 0) {
      0
    } else if (n == 1) {
      1
    } else if (i < n) {
      loop(b, a + b, i + 1)
    } else {
      a + b
    }
  }

  loop(0, 1, 2)
}

nになるまで最初から2つの数字を足していく考え方です。
そして解答はこちらです。

def fib(n: Int): Int = {

  def loop(n: Int, prev: Int, cur: Int): Int = {
    if (n == 0) {
      prev
    } else {
      loop(n - 1, cur, prev + cur)
    }
  }

  loop(n, 0, 1)
}

こちらはnが0になるまでデクリメントしながら2つの数字を足していき、0になったらそれまでの値を返しています。

僕の方はforループ的な考え方なのですが、解答の方はより再帰的な考え方になっているのかなと思います。より再帰的に考えられることで、こうしてシンプルなコードになるんだなと思いました。

Tweet

ピーター 社員：ピーター, 雑記