Preface (はじめに)
再帰関数を用いてフィボナッチ数列を出力する.
Fibonacci
フィボナッチ数を返す関数fibは以下のような関係にあります.
fib(n) = fib(n-1)+fib(n-2)
0 1 1 2 3 5 8 13 21 ...
fib(0) = 0
フィボナッチ数列の初項fib(0)は0と定義されているので
fibonacci.rb
def fib(n)
if n==0
return 0
end
end
とします.
このテストに前回作ったassert_equalを使います.
fibonacci.rb
require './assert_equal'
puts assert_equal(0, fib(0))
出力は
> ruby fibonacci.rb
expected :: 0
result :: 0
succeeded in assert_equal.
ちゃんと期待通り動きました.
fib(1) = 1
フィボナッチ数列の第二項fib(1)は1と定義されているので, 上記のコードに加筆します.
fibonacci.rb
require './assert_equal'
def fib(n)
if n==0
return 0
elsif n==1
return 1
end
end
puts assert_equal(0, fib(0))
puts assert_equal(1, fib(1))
出力は
expected :: 0
result :: 0
succeeded in assert_equal.
expected :: 1
result :: 1
succeeded in assert_equal.
これも期待通り.
fib(n) = fib(n-1) + fib(n-2)
ここからさらにnが大きくなってもちゃんとフィボナッチ数を返すようにします.その前にごちゃごちゃしてきたので一度スッキリさせます.
fibonacci.rb
def fib(n)
return 0 if n==0
return 1 if n==2
end
さらにfib(n) = fib(n-1) + fib(n-2)の処理を加えます.
fibonacci.rb
def fib(n)
return 0 if n==0
return 1 if n==1
return fib(n-1) + fib(n-2)
end
確認のためのテストもArray.eachを使ってキレイにする.
fibonacci.rb
[[0,0], [1,1],[2,1],[3,2],[4,3],[5,5],[6,8],[7,13],[8,21],[9,34]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
出力は
expected :: 0
result :: 0
succeeded in assert_equal.
expected :: 1
result :: 1
succeeded in assert_equal.
expected :: 1
result :: 1
succeeded in assert_equal.
expected :: 2
result :: 2
succeeded in assert_equal.
expected :: 3
result :: 3
succeeded in assert_equal.
expected :: 5
result :: 5
succeeded in assert_equal.
expected :: 8
result :: 8
succeeded in assert_equal.
expected :: 13
result :: 13
succeeded in assert_equal.
expected :: 21
result :: 21
succeeded in assert_equal.
expected :: 34
result :: 34
succeeded in assert_equal.
これもちゃんと動作した.
おまけ
このままでは, nが大きくなると指数関数的に処理が重くなる.その原因はfib(n)を求めるのにfib(n-1)とfib(n-2)を別々で求めているため.
そこでメモ化再帰という手法で処理を軽くしてみる.
fibonacci_opt.rb
@memo = {}
def fib(n)
return @memo[n] if @memo.has_key?(n)
return 0 if n == 0
return 1 if n == 1
return @memo[n] = fib(n-1) + fib(n-2)
end
puts fib(100)
出力は
> ruby fibonacci_opt.rb
-> 354224848179261915075
この結果は合っていた.