再帰を使ったFibonacci数列



# Fibonacci数列

Fibonacci数列とは

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

で表される\* どの数字も前２つの数字を足した数字 \*という規則を持つ数列です．<br>これを今回は再起を用いて解きます．


# 方法

Rubyの基礎2で作ったassert\_equal.rbを利用してfibonacci.rbを作っていきます.


# 初項

Fibonacci数列の初項は0です．

-   まずは表示させてみます．
    
    ```ruby
    p fib(0)                                                                      
    ```

もちろんありません．

-   defします．
    
    ```ruby
    def fib(n)                                                                    
      if n==0                                                                     
        return 0                                                                  
      end                                                                         
    end                                                                           
    ```
-   assert\_equal.rbを呼び出して，出力を確認してみます.

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

    $ ruby fibonacci.rb
    expected :: 0                                                                 
    result   :: 0                                                                 
    succeeded in assert_equal.                                                    

もちろん0しか返されないのでtrueです．


# 第二項

次はfib(1)=1，初項と同様にやっていきます．<br>n=1の時をdefに追加

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

テスト用のputsはこんな感じ

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

-   テストを配列に入れてみた方がきれいな感じがする.
    
    ```ruby
    [[0,0],[1,1]].each do |index, expected|                                                  
      puts assert_equal(expected, fib(index))                                    
    end                                                                           
    ```


# 以降

これ以降はfib(n) = fib(n-1)+fib(n-2)を使っていきます．0と1でない値の時にreturnできるようにします．<br>defに追加，テストには第三項を追加

```ruby
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]].each do |index, expected|
  assert_equal(expected), fib(index))
end
```

出力してみる

    $ ruby fibanacci.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.

全てtrueなのでいい感じ


# テストを追加

追加後のプログラムはこんな感じ

```ruby
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|
  assert_equal(expected), fib(index))
end
```

完成．終わり



------
 - **source** ~/Desktop/grad_members_20f/members/mm-cell/post_org/fibonacci.org