More than 3 years have passed since last update.

Ruby 勉強メモ(再帰関数)

Posted at 2020-12-31

概要

今回は繰り返し処理の勉強をしたメモを残します。for文でもよいのですがforと再帰、両方を勉強したほうが良いため、今回のテーマは再帰です。
再帰関数の練習としてフィボナッチ数列を実装します

フィボナッチ数列といえば、
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
というようにn項目が(n-1)と(n-2)項目の足し算で表される数列であった。漸化式で書くとこうなる。

\begin{align}
a_n &=  0 \quad|\quad n=0\\
&= 1 \quad|\quad n=1\\
&= a_{n-2}+a_{n-1} \quad|\quad otherwise
\end{align}

def fibonacci(n)
    return 0  if n==0   # 漸化式1項目
    return 1  if n==1   # 漸化式2項目
    return fib(n-2)+fib(n-1)   # 漸化式3項目
  end

p fibonacci(8)