再帰

1. 再帰とは
2. 階乗
3. ユーグリッドの互除法
4. フィボナッチ数列

1.再帰とは

再帰的（recursive）アルゴリズムはアルゴリズムでの基本的手法の一つです。Recursive という言葉は帰納的と訳される場合もあります。帰納的関数と再帰的関数と言う場合，これらは本質的には同じです。しかし，inductive も帰納と訳されます。数学的帰納法の帰納は inductive の方です。

一般に再帰と帰納は，少しニュアンスの違いがあります。

その定義の中に，更にその定義されるべきものが，簡単化されて，含まれているとき，　あるものが定義されている場合，

それは「再帰的である」と言われます。循環論法に似ていますが，少し違います。再帰的はその部分に含まれるものが全く同じものではなくて，簡単になったもので，最終的終了条件が明示されているものです。

引用元URL: http://ews2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Recursive.html

2.階乗

!10 = 10×9×8×7×6×5×4×3×2×1

def factorial(n)
  return 1 if n == 0
  n * factorial(n - 1)
end 

3.ユークリッドの互除法

まず再帰なしで書いてみた

def euclidean(a, b)
  while true
    result = a % b
    return b if result == 0
    a, b = b , result
  end
end

一応実行でて、正しい結果が出た。

4.フィボナッチ数列

まず再帰なしで書いてみた

def fibo(n)
  arr = [1, 1]
  (n-2).times do
    arr << arr[-1] + arr[-2]
  end
  return "#{arr} ｜#{n}番目は#{arr[-1]}"
end

一応実行でて、正しい結果が出た。

Fibonacci sequence in Ruby (recursion) - Stack Overflow

Lazy fibonacci in Ruby - Stack Overflow

ruby - Fibonacci One-Liner - Stack Overflow