目標
fibonacci数列を求めるプログラム(fibonacci.rb)を使い,再帰を理解する.
解説
フィボナッチ数列とは
フィボナッチ数列(fib(n))は以下の漸化式で表すことが出来ます.
fib(0)=0
fib(1)=1
fib(n+2)=fib(n)+fib(n+1) n>=0
これらを求めるプログラムを作っていきます.
fib(0) = 0の時
フィボナッチ数列の初項を表示します．
def fib(n)
if n==0
return 0
end
end
その際に前回assert_equalを使い,第1項と第2項とそれ以外を判定するものを作成します.
require './assert_equal_final.rb'
puts assert_equal(0, fib(0))
requireで他のプログラムを持ってくることが出来ます.
fib(1) =1の時
次は第2項を表示します.
def fib(n)
if n==0
return 0
end
if n==1
return 1
end
end
ここから配列を使ってテストを行っていきます.
require './assert_equal_final.rb'
[[0,0],[1,1]].each do |pair|
puts assert_equal(pair[0], fib(pair[1]))
end
fib(2) = fib(1) + fib(0) = 1の時
次は第3項を表示していきます.
def fib(n)
if n==0
return 0
end
if n<=2
return 1
end
end
それに伴って配列の受け取り方を少し変えます.
require './assert_equal_final.rb'
[[0,0],[1,1],[2,1]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
第3項を表示するプログラムは以下のように簡略化できます.
def fib(n)
return 0 if n==0
return 1 if n<=2
end
fib(n+2) = fib(n) + fib(n+1)
一般項はfib(n) = fib(n-1) + fib(n-2)として扱います.
require './assert_equal_final.rb'
def fib(n)
return 0 if n==0
return 1 if n==1
return fib(n-1)+fib(n-2)
end
[[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.
参考にしたサイト
この記事を書くために以下のサイトを参考にしました.チャート式ruby-V(Recursive Fibonacci)
- source ~/grad_members_20f/members/Takahiro-Nishikawa/ruby_fibonacci.org