Recursive Fibonacci (フィボナッチ数列)

Fibonacci数列とは

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) (n >= 0)
0 1 1 2 3 5 8 13 21 34 55 ...

の漸化式で定義される数列である.

お題

フィボナッチ数列をrecursion(再帰)で求める．

動作確認には assert_equal を使用

require './assert_equal'

fib(0) = 0

まずは初項の0から表示してみる

関数 fib を作成する

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

fib(1) = 1

次はfib(1) = 1を表示させる

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

fib(2) = fib(1) + fib(0) = 1

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

これでは正常に動作確認できないので，以下のように変更する.

require './assert_equal'
[[0,0],[1,1],[2,1]].each do |index, expected|
  puts assert_equal(expected, fib(index))
end

puts assert_equal(expected, fib(index))end#+end_src

コード削減

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

これで2行に削減できる．このほうがスマートで見やすい. 見やすさを意識してコーディングする.

fib(n) = fib(n-1) + fib(n-2)

第1項は n = 1 なら 1 を返すようにし, 第2項以降は再帰で値を返すようにすると以下のようになる

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

となる.

そうすると最終的なコードは，

require './assert_equal_richer_output.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-IV(Recursive Fibonacci)

---

• source ~/grad_members_20f/members/djj31370/c5_fibonacci.org