!Mac OS X-10.15.7 !ruby-2.6.3p62
Recursion
例題
フィボナッチ数列を求める.
fib(n) = fib(n-1)+fib(n-2)
0 1 1 2 3 5 8 13 21 ...
fib(0) = 0
Fibonacci数列の初項は0まずは, 関数にしてしまう.
def fib(n)
if n==0
return 0
end
end
前回作ったassert_equal.rbのassertionで出力と期待値が一致しているかどうか確認
#+begin_src ruby
require './assert_equal'
puts assert_equal(0, fib(0))
結果
expected :: 0
result :: 0
succeeded in assert_equal.
fib(1) = 1
n = 1の時を確認.
require './assert_equal'
def fib(n)
if n==0
return 0
end
if n==1
return 1
end
end
assert_equal(0, fib(0))
assert_equal(1, fib(1))
fib(2) = fib(1) + fib(0) = 1
require './assert_equal'
def fib(n)
if n==0
return 0
end
if n<=2
return 1
end
end
[[0,0],[1,1],[2,1]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
配列の受け取りをより明示的にする/.
index, expected = pair
と修正できるので,以下のように修正
[[0,0],[1,1],[2,1]].each do |index, expected|
puts assert_equal(pair[1], fib(index))
end
fib(3) = 2 = fib(2) + fib(1)
以下コード.
def fib(n)
return 0 if n==0
return 1 if n<=2
return fib(2) + fib(1)
end
最終形
fib(2) = fib(1) + fib(0) = 1 + 0
上記が抜けているため, if文の条件分岐をもう少し狭める.
最終的に,
require './assert_equal'
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]].each do |index, expected|
puts assert_equal(expected, fib(index))
end
結果
> ruby fobonacci.rb
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
上手く動作したことがたしかめられた.
参考サイト
https://qiita.com/daddygongon/items/1bb27b8920c201d5c520
- source ~/my_ruby/grad_members_20f/members/drop-sd/lectures/no10.org