【Week 10】recursion, ruby_fifth



# はじめに

マルチスケールシミュレーション特論の講義メモです．講義メモのインデックスは[コチラ](<https://qiita.com/e79a93e5b7b1/items/d48ad7b8df544d737a78>)

今回の参考資料は[チャート式ruby-V(Recursive Fibonacci)](<https://qiita.com/daddygongon/items/1bb27b8920c201d5c520>)です．


# チャート式 Ruby

参照記事は[コチラ](<https://qiita.com/daddygongon/items/1bb27b8920c201d5c520>)


## fibonacci

フィボナッチ数列とは

    0 1 1 2 3 5 8 13 21 ...

のように

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

を満たす数列である．この関数 fib をテスト駆動開発で作成していく．

テスト駆動開発ではとりあえず出力してみて，期待する出力と異なっていれば修正していくような進め方をする．今回は 1 つずつ項を追って，プログラムを完成させる．


### fib(0) = 0

フィボナッチ数列の初項は 0 なので，関数 fib は

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

puts fib(0)
```

期待する出力と等しいか確認したいので，前回作成した assert\_equal を使って確認する．

```ruby
require './assert_equal_final.rb'

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

puts assert_equal(0,fib(0))
```

実行すると

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

期待通りの出力が得られた．assert\_equal 便利！


### fib(1) = 1

続いて第 2 項は 1 なので，関数 fib は

```ruby
require './assert_equal_final.rb'

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

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

実行すると

    > ruby fibonacci.rb
    expected :: 1
    result   :: 1
    succeeded in assert_equal.

期待通りの出力が得られた．ここで，テスト部分の書き換えを楽にするために，少し改変する．

```ruby
require './assert_equal_final.rb'

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

[[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],[1,2]].each do |pair|
```

と追加して，実行すると

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

0, 1 以外は定義されてないので仕方ないよね．それでは 2 のときの条件も追加する．

```ruby
require './assert_equal_final.rb'

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

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

ついでに each 文の受け渡しもよりわかりやすいように改良しておく．

if 文が重くなってきたが，条件文は 1 行で表すことができるので忘れずにリファクタリングする．

```ruby
require './assert_equal_final.rb'

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

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


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

続いて第 3 項．まずはテスト．

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

    > ruby fibonacci.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.
    
    expected :: 2
    result   :: 
    failed in assert_equal.

仕方ないです．TDD はまず green にすることが大切だそうなので，

```ruby
require './assert_equal_final.rb'

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

[[0,0],[1,1],[2,1],[3,2]].each do |index, expected|
  puts assert_equal(expected,fib(index))
end
```

さすがに強引すぎる気がする．

アルゴリズム的に正しくは

    return fib(2) + fib(1)

なので

```ruby
require './assert_equal_final.rb'

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

[[0,0],[1,1],[2,1],[3,2]].each do |index, expected|
  puts assert_equal(expected,fib(index))
end
```

実行すると

    > ruby fibonacci.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.
    
    expected :: 2
    result   :: 2
    succeeded in assert_equal.

このときf(2)ってずっと呼び出されるんじゃあ…

うまくいってるのがよくわからない．


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

続いて第 4 項．まずはテスト．

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

    > ruby fibonacci.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.
    
    expected :: 2
    result   :: 2
    succeeded in assert_equal.
    
    expected :: 3
    result   :: 2
    failed in assert_equal.

もちろんエラーが出る．

3 つ目の return を定義通り

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

と修正する．このとき

```ruby
return 1 if n == 1
```

でよいので，最終的には以下のようなプログラムとなる．

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

実行すると

    > ruby fibonacci.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.
    
    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.

問題なくフィボナッチ数列の関数 fib をテスト駆動開発で作成できた．


# Ruby 開発周辺情報

今回はチャート式 Ruby のみです．


# 次回の講義内容 <span class="timestamp-wrapper"><span class="timestamp">&lt;2020-12-02 Wed&gt;</span></span>

次回の講義は

-   [チャート式ruby-VI(hello class)](<https://qiita.com/daddygongon/items/969ad5112878f6dab844>)

だそうです．



------
 - **source** ~/grad_members_20f/members/e79a93e5b7b1/posts/class/c10_20201125.org