今回は再帰メソッドを用いてフィボナッチ数列を求めるプログラムを作成します．

フィボナッチ数列とは

フィボナッチ数列は「1番目と二番目の数値は1であり，三番目以降の数値は直前の2数の和である数列」のことであり，以下の漸化式で定義される．

$$ F_{0} = 0$$

$$ F_{1} = 1$$

$$ F_{2} = 1$$

$$ F_{n+2} = F_{n+1} + F_{n} (n \geq 0)$$

フィボナッチ数列は，再帰的な関数を利用して作成することができる．

再帰メソッドとは

再帰とは，プログラム上で再度呼び出すことである．例えば以下のようなプログラムがある．


def sum(array)
 return 0 if array.empty?
 top=array.shift
 top+sum(array)
end

p sum([1,2,3,4,5]) # =>15

プログラム

それでは初めに第0項と第1項及び第2項を実装するところから始める．


def fib(n)
 #第0項の場合
 if n==0 then
  return 0

 #第1項の場合
 else n<=2 and n!=0 then
  return 1  
 end
end

次に，第n項の実装を行う．第n項は

$$F_{n}=F_{n-1}+F_{n-2} $$

で求めることができるので

def fib(n)
  #第0項の場合
  if n==0 then
   return 0

  #第1項の場合
  else n<=2 and n!=0 then
   return 1

  #第n項( n>2 )の場合
  else
   return fib(n-2)+fib(n-1)
  end
end

for n in 0..10 do
 print 'n=',"#{n} ",' fib=',"#{fib(n)}", "\n" 
end

と書けばよい．ここで，実行結果が正しいか否かを検証するために，前回作成したプログラムassert_equal_finを用いる．念のため，プログラムのソースコードを以下に記す．

assert_equal_fin.rb


require 'colorize'

def puts_vals(expected, result)
  puts "expected :: #{expected}"
  puts "result   :: #{result}"
end
def assert_not_equal(expected, result)
  puts_vals(expected, result)
  print expected != result ?
	  "succeeded in #{__method__}.\n".green :
	  "failed in #{__method__}.\n".red
end
def assert_equal(expected, result)
  puts_vals(expected, result)
  print  case expected == result
	 when true  ; "succeeded in #{__method__}.\n".green
	 when false ; "failed in #{__method__}.\n".red
	 end
end

if $PROGRAM_NAME == __FILE__
  assert_equal(1, 1)
  assert_equal(1, 2)
  assert_not_equal(1, 2)
  assert_not_equal(1, 1)
end

それでもって，出力結果の検証部分は以下のようにかく．

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

以上より，プログラムの最終形態は以下のようになる．内容としては，フィボナッチ数列の第0項から第10項までを出力し，assert_equalによっていくつかの項があっているかどうかを検証する．

fibonacci.rb

require './assert_equal_fin'

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

  elsif n <=2 and n!=0 then
    return 1

  else
    return fib(n-2)+fib(n-1)
  end
end

for n in 0..10 do
  print 'n=',"#{n} ",' fib=',"#{fib(n)}", "\n"
end

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

参考文献

https://qiita.com/pokotyan/items/53e92a21805f651173aa

source ~/grad_members_20f/members/NobuakiMori/L10_fibonatti.org