第10回(フィボナッチ数列)

# お題:Fibonacci数列

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

をrecursion(再帰)で求めなさい．

# 解説

# fib(0) = 0

Fibonacci数列の初項は0

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

前回作成したassert\_equal.rbで出力が期待値と一致しているかを確認.

```ruby
require './assert_equal'
puts assert_equal(0, fib(0))
```

結果

    expected :: 0
    result   :: 0
    succeeded in assert_equal

# fib(1) =1

次はfib(1)=1.まずはassertion

```ruby
puts assert_equal(1, fib(1))
```

もちろん失敗するので書き換える.

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

結果

    expected :: 0
    result   :: 0
    succeeded in assert_equal
    expected :: 1
    result   :: 1
    succeeded in assert_equal

これでOK.

テスト側の重複が気になってきたので，配列に

```ruby
[[0,0],[1,1]].each do |pair|
  puts assert_equal(pair[0], fib(pair[1]))
end
```

結果は同じ

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

まずはテスト

```ruby
[[0,0],[1,1],[2,1]].each do |pair|
```

これではダメ.

    > ruby fibonacci.rb
    expeced:0
    result :0
    succeeded in assert_equal
    
    expeced:1
    result :1
    succeeded in assert_equal 
    
    expeced:2
    result :1
    failed in assert_equal

条件分岐をもう少しいじって，

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

これでいけると思うので実行.

    > ruby fibonacci.rb
    expeced :: 0
    result  :: 0
    succeeded in assert_equal
    
    expeced :: 1
    result  :: 1
    succeeded in assert_equal 
    
    expeced :: 2
    result  :: 1
    failed in assert_equal

あれ?

実は，assert\_equalは(expect, result)とうけとっているため配列変数pairの示数indexが逆.

```ruby
require './assert_equal'
[[0,0],[1,1],[2,1]].each do |pair|
  puts assert_equal(pair[1], fib(pair[0]))
end
```

が正解．

## refactoring

もう少し配列の受け取りを明示的にすると，

    index, expected = pair

と修正できて

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

こっちのほうが分かりやすい.

# refactoring

メソッドが長くなってきたので短く書き直す.

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

と2行に削減

# fib(3) = 2 = fib(2) + fib(1)

テストは

    [[0,0],[1,1],[2,1],[3,2]].each do |index, expected|

return 2になってほしいのでfib(2)+fib(1)にする.

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

結果

    > ruby fibonacci.rb
    expeced :: 0
    result  :: 0
    succeeded in assert_equal
    
    expeced :: 1
    result  :: 1
    succeeded in assert_equal 
    
    expeced :: 1
    result  :: 1
    succeeded in assert_equal 
    
    expeced :: 2
    result  :: 2
    succeeded in assert_equal

# fib(4) = fib(3) + fib(2) = 2 + 1 = 3

次は4. 期待値は3

    [[0,0],[1,1],[2,1],[3,2],[4,3]].each do |index, expected|

テスト結果は当然fail.最後のreturnを定義通りに

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

と修正

結果

    > ruby fibonacci.rb
    expeced :: 0
    result  :: 0
    succeeded in assert_equal
    
    expeced :: 1
    result  :: 1
    succeeded in assert_equal 
    
    expeced :: 1
    result  :: 1
    succeeded in assert_equal 
    
    expeced :: 2
    result  :: 2
    succeeded in assert_equal 
    
    expeced :: 3
    result  :: 3
    succeeded in assert_equal

全てsucceed

そのまま続きもやってみる.

    [[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

全部いけた.

ただ一つ抜けているのは，

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

なんで，fibのなかの条件分岐はもう少し狭められて，

    return 1  if n == 1

で十分

最終的に

```ruby
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

[[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
```

------
 - **source** ~/grad_members_20f/members/yoshida/c5_fibonacci.org