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

お題:Fibonacci数列

チャート式Rubyの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本¹に載っていたののアレンジです．chart式の解法，解説，発展のサイクルがめちゃくちゃ短くなって，TDDのred, green, refactoringに対応している感触を掴んでください．

前回作ったassert_equal.rbをcodes(作業directory)にcopyしておいてください．

fib(0) = 0

Fibonacci数列の初項は0です．

• red: まずは表示させてみます．

  p fib(0)
  

  ないよね．

• green: そこで，defします．

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

• refactoring: assert_equal.rbのassertion(確認)を試しておきます．

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

fib(1) = 1

次はfib(1)=1

• red: まずはassertion

puts assert_equal(1, fib(1))

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

• green: コピペ．

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

これで通る．

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

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

テストはもちろんgreen.

refactoring

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

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

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

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

さらによく見ると

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

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

fib(2) = 1

red

まずはテスト

[[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を増やして，

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

これで動くはず… おやおや．

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

result = fib(2)
expected = 1

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

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

と修正できて

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は

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は

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ももちろん．

最終形は，

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万歳!!²

参照文献

---

• source ~/git_hub/ruby_docs/chart_style_ruby/c5_fibonacci.org

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

2. 「TDD死すとも，testingは死せず」"TDD is dead. Long live testing." by David Heinemeier Hanssonってのもありますが．．． ↩