はじめに

再帰関数の学習において、よく題材として取り上げられるフィボナッチ数列の計算について、学びとなったことを備忘録としてまとめました。
本記事では、まず関連する言葉の意味を確認し、以降はフィボナッチ数列の計算プログラムを、再帰を用いた場合と用いていない場合とで、いくつかパターンを記載しております。

言葉の意味

再帰

Wikipediaによると「再帰（recursion）」は以下のように定義されています。

あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。

「再帰関数」とは、再帰的定義された関数（手続き）のことで、処理の中にその関数自身を呼び出す記述があるもののことをいいます。
自分自身を呼び出す関数ともいえます。
※Ruby向けの表現だと、自分自身を呼び出すメソッド。
また、関数が自分自身を呼び出して実行することを「再帰呼び出し」といいます。

フィボナッチ数列

「フィボナッチ数列（Fibonacci sequence）」は、 1 つ前の項と 2 つ前の項を足し合わせていくことでできる数列です。
次の漸化式で定義されます。

$F_0 = 0$,
$F_1 = 1$,
$F_{n+2} = F_n + F_{n+1}$ $(n ≥ 0)$

$n$ 番目のフィボナッチ数を求める漸化式は以下のように定義できます。

$F_0 = 0$,
$F_1 = 1$,
$F_n = F_{n-1} + F_{n-2}$ $ (n=2,3,…)$

数列は以下のように続きます。
$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …$

第 0 項を $0$, 第 1 項を $1$ とし、それ以降は前の 2 項の和となっています。
例えば第 6 項は、第 5 項である $5$ と第 4 項である $3$ を足した $8$ となります。

漸化式

ある項をそれ以前の項を用いて表す等式のことです。
$n$ 番目と $n+1$ 番目の関係（隣接している 2 項の関係）を式で表したものを、隣接二項間漸化式と呼び、$n$ 番目と $n+1$ 番目と $n+2$ 番目の関係（隣接している 3 項の関係）を式で表したものを、隣接三項間漸化式と呼びます。

例えば、以下の漸化式は、
$a_{n+1} = 2a_n + 3$
「 $n+1$ 番目の数」は、それ以前の項である「 $n$ 番目の数」を 2倍し、それに3を足したものを意味します。

フィボナッチ数列の漸化式でいうと、
$F_{n+2} = F_n + F_{n+1}$
「 $n+2$ 番目の数」は、それ以前の項である「 $n$ 番目の数」と「 $n+1$ 番目の数」を足したものを表しています。

「漸化式」は英語表記だと（recurrence relation）で、「再帰関係式」と訳すこともあり、Wikipediaでは、

各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式である。

と定義されています。
以上のことから、漸化式で表せるフィボナッチ数列は、再帰を用いたプログラムで表現できると推測できます。

漸化式を元にフィボナッチ数を求めるプログラムを作成

Ruby でコードを書いてみる

$F_0 = 0$,
$F_1 = 1$,
$F_n = F_{n-1} + F_{n-2}$ $ (n=2,3,…)$

上記の漸化式を元に、再帰を用いたプログラムを記述します。

# 指定番のフィボナッチ数を求めるメソッドを定義
def fibonacci(num)
  # 再帰終了条件
  if num == 0
    return 0
  # 再帰終了条件
  elsif num == 1
    return 1
  else
    # 再帰呼び出し
    fibonacci(num - 1) + fibonacci(num - 2)
  end
end

# 第 0 項から第 9 項までを出力
(0..9).each do |i|
  puts "第 #{i} 項： #{fibonacci(i)}"
end

仮引数を num として、 fibonacci という名のメソッドを定義しています。
fibonacciメソッド内では if で条件分岐します。
num が受け取る値が $0$ の場合（再帰終了条件）、 $0$ を返します。
num が受け取る値が $1$ の場合（再帰終了条件）、 $1$ を返します。
num が受け取る値が $0$ もしくは $1$ 以外の場合、 fibonacciメソッドを再帰的に呼び出します。
呼び出すのは 2 つ分の fibonacciメソッドで、num から $1$ を引いた値と num から $2$ を引いた値をそれぞれ引数として渡し、呼び出します。
呼び出した先で num が受け取る値が $0$ もしくは $1$ 以外の場合、また fibonacciメソッドを再帰的に呼び出します。この動作をそれぞれの呼び出し先で num が $0$ もしくは $1$ になるまで（再帰終了条件に達するまで）行います。
「呼び出し先の num が $0$ もしくは $1$ になった時点で、戻り値を呼び出し元に返す」というのが連鎖的に行われ、その過程で値が足し合わさって、最終的に求める値となります。

このプログラムを実行した結果が以下になります。

第 0 項： 0
第 1 項： 1
第 2 項： 1
第 3 項： 2
第 4 項： 3
第 5 項： 5
第 6 項： 8
第 7 項： 13
第 8 項： 21
第 9 項： 34

再帰の動きと評価結果

再帰の動きはイメージしづらいため、第 5 項のフィボナッチ数を求める場合の動きと評価結果の流れを以下に示します。（メソッド名を fibo としています）

                                 fibo(5)
                               /         \
                        fibo(4)            fibo(3)
                      /      \              /      \
               fibo(3)      fibo(2)        fibo(2)   fibo(1)
             /    \        /     \           /    \
      fibo(2)  fibo(1)  fibo(1)  fibo(0)  fibo(1)  fibo(0)
      /    \
 fibo(1)  fibo(0)

fibo(5)
↓
fibo(4) + fibo(3)
↓
(fibo(3) + fibo(2)) + (fibo(2) + 1)
↓
((fibo(2) + 1) + (1 + 0)) + ((1 + 0) + 1)
↓
(((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)
# => 5

問題点

以上が、フィボナッチ数列の漸化式をそのままコードに落とし込んだプログラムでした。
しかし、このプログラムには欠点があります。
それは、求めたい項の値が大きい場合、計算量が増えすぎてしまい、処理にかなりの時間がかかる or タイムアウトになる、ということです。
計算量が膨大になる理由は、再帰呼び出しの際に、メソッドを 2 つ呼び出している点にあります。
1 つのメソッドから 2 つのメソッドが枝分かれ的に呼び出され、その片方からまた 2 つのメソッドが呼び出され、もう片方からも 2 つのメソッドが呼び出され、、、とやるべき計算処理が増えていきます。
その後、呼び出されたメソッド内で再帰終了条件が満たされ、終了条件の処理によって得られた結果を基に、順に計算が行われていき（段々とやるべき計算処理が減っていき）、最終的に求めたい値を得ることができます。
計算過程において、このように計算が遅延され、膨張し、収縮するプロセスのことを「再帰的プロセス」と呼びます。

例えば、第 5 項のフィボナッチ数を求める場合、 fibo(5) の計算は、
fibo(4) を1回，
fibo(3) を2回，
fibo(2) を3回，
fibo(1) を5回，
fibo(0) を3回
行うことになります。

これでは、同じ計算を 2 回も 3 回も行っていて効率が悪いです。大きな項についてもスムーズに処理できるよう、計算の重複をなくし、計算量を抑えることが求められます。

続いてはこの問題を解消したプログラムについて考えます。

メモ化再帰

一度行った計算結果を保存しておき、同じ引数による関数呼び出しがあった場合は、保存した結果を返すことを「メモ化再帰」と呼びます。
メモ化（memoization）は処理の高速化を図る最適化技法の一種です。
計算結果の保存先として、配列やハッシュを用います。

以下、フィボナッチ数の第 50 項を出力するプログラムを作成します。
※作成するプログラムはあくまでも一例です。

配列にメモするプログラム

配列にメモする場合、添字（インデックス）が項、要素がフィボナッチ数を表します。

$memo = []

def fibonacci(num)
  if num == 0
    return 0
  elsif num == 1
    return 1
  else
    return $memo[num] ||= fibonacci(num - 1) + fibonacci(num - 2)
  end
end

puts fibonacci(50)
# => 12586269025

「||=」は「||」演算子の自己代入演算子で、左辺が偽か未定義ならば右辺を代入します。

参考：Rubyで使われる記号の意味（正規表現の複雑な記号は除く） (Ruby 3.0.0 リファレンスマニュアル)

if $memo[num] != nil
  return $memo[num]
else
  return $memo[num] = fibonacci(num - 1) + fibonacci(num - 2)

このコードを簡素に書き換えたものが、

return $memo[num] ||= fibonacci(num - 1) + fibonacci(num - 2)

になります。

fibonacci(5) を求める場合、はじめ、配列 $memo には要素が入っておらず、初期状態は空です。
処理の過程で初めてfibonacci(3)を呼び出した際には $memo[3] == nil で未定義であるため、 $memo[3] には fibonacci(2) + fibonacci(1) の計算結果が代入されます。
以降、fibonacci(3)の計算は、 $memo[3] が既に定義されているので、わざわざ fibonacci(2) と fibonacci(1) を呼び出すことをせず、 $memo[3] の値をリターンします。

ハッシュにメモするプログラム

ハッシュにメモする場合、キーが項、バリューがフィボナッチ数を表します。

$memo = {}

def fibonacci(num)
  if $memo.has_key?(num)
    return $memo[num]
  elsif num == 0
    return 0
  elsif num == 1
    return 1
  else
    return $memo[num] = fibonacci(num - 1) + fibonacci(num - 2)
  end
end

puts fibonacci(50)
# => 12586269025

今回は has_key?メソッドで項の計算結果がハッシュにメモ済みかどうかを評価します。
メモしてあるならば、 $memo[num] の値をリターンします。

参考：Hash#has_key? (Ruby 3.0.0 リファレンスマニュアル)

メモ化をすることで無駄な計算を省き、 fibonacci(50)　のような大きな項についても問題なく求めることができます。

メモ化再帰を使わず、再帰呼び出しの回数を抑えたプログラム

これまでのプログラムは、メソッド内で 2 つ分の再帰呼び出しを行なっていました。
次のプログラムでは 1 つ分の再帰呼び出しのみ行い、計算量の増加を抑えています。

def fib1(num)  # → 《 1 》
  # 初期値を渡す
  return fib2(0, 1, num)  # → 《 2 》
end

def fib2(a, b, c)  # → 《 3 》
  # 再帰終了条件
  if c < 1  # → 《 5 》
    return a
  else
    # fib2メソッドの再帰呼び出しでは、1 番目の引数に現在のフィボナッチ数を、 2 番目の引数に 1 つ前のフィボナッチ数を渡している
    return fib2(a + b, a, c - 1)  # → 《 4 》
  end
end

puts fib1(50)
# => 12586269025

以下、コード上のコメントの番号に対応した説明書きとなっています。

求めたい項を（引数として）受け取るための fib1メソッドを定義しています。《 1 》
fib1 メソッドの中で、項を求めるための処理を記述した fib2メソッドを、初期値として第一引数には $0$ 、第二引数には $1$ 、第三引数には fib1 で受け取った求めたい項の値を渡し、呼び出しています。《 2 》
fib2 メソッドは、渡された引数から次のフィボナッチ数を求める再帰処理を行う、もしくは再帰終了条件を満たしたときに求めたいフィボナッチ数を返す、という処理を行うメソッドです。《 3 》
再帰呼び出しの際に、第一引数（実引数）に現在のフィボナッチ数 a + b を、第二引数（実引数）に 1 つ前のフィボナッチ数 b を渡しています。《 4 》
呼び出し先では、再帰終了条件を満たさない場合、次のフィボナッチ数を求めるための再帰呼び出しを行います。
「求めたい次のフィボナッチ数」目線で考えると、呼び出し先で受け取った第一引数（仮引数） a が　1 つ前のフィボナッチ数で、第二引数（仮引数） b が 2 つ前のフィボナッチ数に該当するので、それらを足し合わせた和が「求めたい次のフィボナッチ数」となります。《 3 》¹
fib2メソッドの第三引数 c はカウンタ（何回再帰処理を行うかの指標であり、再帰終了条件に辿り着くために渡される引数）としての役割を担っており、再帰呼び出しが行われるたびに $-1$ されます。《 2 》
呼び出し先で、 c が $1$ 未満になったとき（再帰終了条件を満たしたとき）に現在のフィボナッチ数 a を返すようにしています。《 4 》

プロセスの状態を表す変数を各引数に渡し、その状態を変更させていき、再帰終了条件を満たしたときに、その状態から計算結果を返します。これを「反復的プロセス」と呼びます。
反復的プロセスは再帰的プロセスと異なり、計算が膨張、縮小せず、固定長のスペースで計算することができます。そのため、「末尾再帰的（tail recursive）」とも呼ばれます。この場合、余分なスペースを必要としないため効率的に実行することができます。
また、その状態が将来的なシステムの動作を制御する変数のことを「状態変数（state variable）」と呼びます。

再帰を使わないプログラム

これまで散々再帰を用いてコードを書いてきましたが、フィボナッチ数は再帰を使わなくても求めることができます。
以下、 while による繰り返し処理を用いたプログラムです。

def fibonacci(num)
  if num == 0
    return num
  elsif num == 1
    return num
  else
    fibo = 0
    fibo0 = 0
    fibo1 = 1

    i = 1
    while i < num
      fibo = fibo0 + fibo1

      fibo0 = fibo1
      fibo1 = fibo
      
      i += 1
    end

    return fibo
  end
end

puts fibonacci(50)
# => 12586269025

第 0 項から順に求めたい項まで繰り返し処理を行います。
メソッドの中では、求める項を fibo 、その 1 つ前の項を fibo1 、 2 つ前の項を fibo0 として定義します。
fibo0 の初期値として第 0 項である $0$ を、 fibo1 には初期値として第 1 項である $1$ をそれぞれ代入します。
i を初期値 $1$ として定義し、これをカウンタとして用います。
while での繰り返し処理では、 fibo0 + fibo1 （前 2 項の和）を fibo に代入します。
その後、フィボナッチ数の次の項を求めるための準備として、 fibo0 に次回の計算において 2 つ前の項となりうる fibo1を代入し、 fibo1 には次回の計算において 1 つ前の項となりうる fiboを代入します。
この処理を、最終的に求めたい項に達するまで続け、その値をリターンします。

このように、再帰を使わなくても繰り返し処理で十分フィボナッチ数列の計算はできます。

再帰的アルゴリズムのポイント

再帰終了条件を設ける → これがないと無限ループに陥ってしまう
自身の引数より”簡単”な引数を用いて自分自身を呼び出す

再帰の本質は、大きな問題を同じ形をした小さな問題に帰着させることです。
今回のフィボナッチ数列のプログラムでいうと、 fibonacciメソッドに渡す引数を、段々と小さくしていく（元の問題に比べてより小さな問題になるようにメソッドを呼び出す）ことで、最終的に再帰終了条件に辿り着き、その結果を返すという処理が行われています。

以上、至らない点などありましたらご教示頂けると幸いです。

※ 補足
呼び出し元で〈現在のフィボナッチ数〉として渡した a + b が、呼び出し先では《 1 つ前のフィボナッチ数》として扱われ、呼び出し元で〈 1 つ前のフィボナッチ数〉として渡した b が、呼び出し先では《 2 つ前のフィボナッチ数》として扱われることになります。 ↩