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



# お題:Fibonacci数列

[チャート式Ruby](https://qiita.com/daddygongon/items/6f38d9a04e127a7952a7)の5回目，recursion(再帰)です．

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

| index | n      | 0 | 1 | 2 | 3 |
|:------|:-------|--:|--:|--:|--:|
| val   | fin(n) | 0 | 1 | 1 | 2 |

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


# 解説

以下はTDDのバイブルのKent Beck本[^TDDbyKentBeck]に載っていたののアレンジです．chart式の解法，解説，発展のサイクルがめちゃくちゃ短くなって，TDDのred, green, refactoringに対応している感触を掴んでください．

[前回](https://qiita.com/daddygongon/items/f6cea87314ee26e130ea)作ったassert\_equal.rbをcodes(作業directory)にcopyしておいてください．


# fib(0) = 0

Fibonacci数列の初項は0です．

-   **red:** まずは表示させてみます．
    
    ```ruby
    p fib(0)
    ```
    
    ないよね．
-   **green:** そこで，defします．
    
    ```ruby
    def fib(n)
      if n==0
        return 0
      end
    end
    ```
-   **refactoring:** assert\_equal.rbのassertion(確認)を試しておきます．
    
    ```ruby
    require './assert_equal'
    puts assert_equal(0, fib(0))
    ```


# fib(1) = 1

次はfib(1)=1

-   **red:** まずはassertion

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

もちろん失敗するが．．．

-   **green:** コピペ．

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

これで通る．

-   **refactoring:** テスト側の重複が気になってきたので，配列にしよう．

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

テストはもちろんgreen.


# refactoring

ここらへんまで来るとcodeがごちゃついてきた感じしません？しない？　それは頭のいい人．私には無理．えっと，rubocopという汚いcodeの取り締まり警官は10行以上のmethodがあると，烈火のごとく怒ります．

治しようがないと思わずに削減を考えます．求めよさらば与えられん．そんなに無理しなくても，

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

と2行に削減できます．この記法も英語的でしょ．それがrubyのいいところ．これだと何をしているのか一目瞭然でしょ．動いた部分を隠すというのがありますが，こっちの方がスマートです．だからrefactoring(因数分解をもう一度)って名付けられています．

さらによく見ると

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

と一行になることにも気がつくはず．


# fib(2) = 1


## red

まずはテスト

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

なんですが，これはred.

    > ruby fibonacci_2.rb
    expected:0
    result :0
    succeeded in assert_equal 0 should be expected.
    
    expected:1
    result :1
    succeeded in assert_equal 1 should be expected.
    
    expected:2
    result :1
    failed in assert_equal 1 should be expected.


## green

returnを増やして，

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

これで動くはず&#x2026; おやおや．

実は，assert\_equalは(expected, actual)とうけとっています．

    result = fib(2)
    expected = 1

だから，テストは配列変数pairの示数indexが逆で，

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

が正解．そうするとgreen.


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

の方がいいかも，圧倒的にいい〜〜．


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


## red & green

人間は賢いから上のように書いても納得するけど，computerはだめ．sourceは

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

でまずはgreenにしています．


## refactoring

そのあとでcodeを修正します．return 1の意味を考えると

    return 0+1

ですよね．さらには

    return fib(0) + fib(1)

というのも気がつくはず．そうするとcodeは

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

です．これで通るのが不思議かもしれませんが，とおりますし，意味もokです．


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


## red & green & refactoring = magic

次は3項目. 期待値は2ですね．

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

としましょう．テストはもちろんredです．最後のreturnを定義通り

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

と修正しましょう．

そうするとあら不思議．通ります．そのさき1,1,2,3,5,8,13,21ももちろん．

最終形は，

```ruby:sample
def fib(n)
  return n if n<=1
  return fib(n-1) + fib(n-2)
end

require './assert_equal'
[[0,0],[1,1],[2,1],[3,2],[4,3],
[5,5],[6,8],[7,13],[8,21]].each do |index, expected|
  puts assert_equal(expected, fib(index))
end
```

です．


# まとめ

うーーーん．こんなに綺麗にFibonacciを説明できるなんて．TDD万歳!\![^DHH]


# 参照文献

[^TDDbyKentBeck]: テスト駆動開発, Kent Beck (著), 和田 卓人 (翻訳), オーム社; 新訳版 (2017/10/14).

[^DHH]: [「TDD死すとも，testingは死せず」"TDD is dead. Long live testing." by David Heinemeier Hansson](https://dhh.dk/2014/tdd-is-dead-long-live-testing.html)ってのもありますが．．．



------
 - **source** ~/git_hub/ruby_docs/chart_style_ruby/c5_fibonacci.org