授業10回目：Recursion(再帰)

参考サイト

チャート式ruby-V(Recursive Fibonacci)

再帰(Recursive)とは

関数内の振る舞いのうち、自分自身を呼び出す処理のこと.

お題：フィボナッチ数列

フィボナッチ数は、以下の式に基づいて定義される.
参考：wikipedia:フィボナッチ数

fib(n) は n 番目のフィボナッチ数を表すとする
・ fib(0) = 0
・ fib(1) = 1
・ fib(n) = fib(n-1) + fib(n-2)

n = 0 ～ 10 番目のフィボナッチ数を並べると 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

こうしてできるフィボナッチ数列を再帰処理で求める

実装例

fib(n) = fib(n-1) + fib(n-2)　のルールでは求められない n = 0,1 から求めよう

require './assert_equal.rb'

def fib(n)
  if n = =0
    return 0
  end
  if n = =1
    return 1
  end
end

puts assert_equal(0, fib(0))
puts assert_equal(1, fib(1))

第9回の assert_equal が再登場. 1行目の宣言により呼び出し可能になる.
今回の assert_equal のお仕事は関数 fib がちゃんと動いているかのテストである.

assert_equal の重複が気になるので配列にしてしまう. (リファクタリング)

test = [[0,0],[1,1]]
test.each do |index, expected|
  puts assert_equal(index, fib(index))
end

記述を綺麗にしつつ、fib(n) = fib(n-1) + fib(n-2) の部分を作る.

require './assert_equal.rb'

def fib(n)
  return 0 if n==0 
  return 1 if n==1
  return fib(n-1) + fib(n-2)
end

test = [[0,0],[1,1],[2,1],[3,2],[4,3],
	[5,5],[6,8],[7,13],[8,21],[9,34]]
test.each do |index, expected|
  puts assert_equal(expected, fib(index))
end 

出力結果はこんな感じ

["expected", 0]
["result", 0]
true

["expected", 1]
["result", 1]
true

["expected", 1]
["result", 1]
true

["expected", 2]
["result", 2]
true

["expected", 3]
["result", 3]
true

["expected", 5]
["result", 5]
true

["expected", 8]
["result", 8]
true

["expected", 13]
["result", 13]
true

["expected", 21]
["result", 21]
true

["expected", 34]
["result", 34]
true

note

・再起はあんまりやりすぎると処理が重くなったり無限ループになったりするので気を付ける.

---

• source ~/grad_members_20f/members/batamon-427/task10.org