はじめに

エンジニアであれば最低限知っておきたいアルゴリズムの知識のうち、再帰関数に関してまとめました。

以下の記事も参考にしてください。
アルゴリズム入門①計算量とソートの基本
 アルゴリズム入門②実用的なソート
 アルゴリズム入門③探索

再帰関数とは

関数の中で自分自身を呼び出すような関数

です。
例えば、nの階乗は

n! = (n-1)×(n-2)...×1-n×(n-1)!

であり、nが1より大きい場合はより小さい部分問題(n-1)の階乗を含んでいます。nが1の時は、1を返すというように再帰関数はそれが必ずどこかで終了するように実装しなければならないことに注意してください。

分割統治法

再帰のテクニックを用いると、問題を分割し、それを再帰的に解き、それを統合することで解くことができます。
これを分割統治法　と言います。
　
例えば、配列arrayの最大値を探す際に、以下のように分割統治法探すことができます。

def find_max(array)
  m = array.size/2
  if m == 1 # 要素数が一つで終了
	return array[0]
  else
	l = find_max(array[0..m-1]) # 前半の問題をsolve
	r = find_max(array[m..-1]) # 後半の問題をsolve
	[l, r].max # 部分問題の解を統合する
  end
end

フィボナッチ数列

再帰を使って、フィボナッチ数列を解いてみましょう。
フィボナッチ数列は以下のような数列です。

\begin{align}
a_0 &= 0\\
a_1 &= 1\\
a_{n+1} &= a_n \;+ a_{n-1}\\
\end{align}

以下がフィボナッチ数列を求めるコードとなります。


def fibonacci(k)
  if k <= 1
    k
  else
    fibonacci(k-2) + fibonacci(k-1) # 分割して、k-2, k-1の場合についてsolveし、統合する。
  end
end

メモ化

上のコードの場合、$a_n$の値を求めるために、$a_{n-1}$, $a_{n-2}$の値をそれぞれ求めているため、計算量が非常に多くなってしまいます。

これを防ぐために、$a_{n-2}$を求めた際に得た値を、$a_{n-1}$を求める際に使うのが、メモ化と言われる手法です。

詳しくは、以下の記事を参考にしてください。
メモ化を知った

練習問題

フィボナッチ数列 | アルゴリズムとデータ構造 | Aizu Online Judge