再帰関数をつくってみる
再帰関数とは、関数の中で自分自身を呼び出す関数のことです。
例えば、以下のコードは再帰関数と言えます。
def hello
puts 'hello!'
hello
end
hello
helloという関数の中で、hello!という文字列を出力した後に、またhello関数が呼び出されています。
ちなみに上のコードを実行してみると、ただひたすらhello!という文字列がずっと出力されます。（rubyだと「SystemStackError」で強制終了されます）
再帰関数を作るというだけだと上記のコードで目的達成ですが、ただ文字列を出力する再帰関数は面白くないので、再帰関数実装の初歩問題として「階乗の計算」を取り上げてみます。
nの階乗を計算するコードを書いてみました。
まずは再帰関数を使わず実装してみます。
res = 1
while n > 0
res *= n
n -= 1
end
puts res
こんな感じでしょうか。
またrubyにはtimesメソッドという便利なメソッドがあるので、そちらを使うと以下のようになります。
res = 1
n.times do |i|
res *= (i + 1)
end
puts res
どちらもnに自然数を渡してあげることで階乗を計算することができます。
ではこれを再帰関数で実装してみます。以下のようなコードになります。
def factorial(n)
if n == 0
1
else
n * factorial(n - 1)
end
end
factorial関数に自然数を渡してあげれば、その階乗の結果を返してくれるプログラムになっています。
慣れていないとどういう処理の流れかが一見わかりづらいので、n = 3の場合を例に処理を追ってみます。
n = 3を引数としてfactionalに渡すと、if-elseブロックでnが評価されて分岐します。n = 3なのでelseの処理が走って、3 * factional(2)が返されます。
しかし返り値にfactional関数を呼び出しているため、ここでも処理が走り、結果が返されます。factional(2)は2 * factional(1)を返します。
同様にして、factional(1)は1 * factional(0)を返します。
ここでfactional(0)はif-elseブロックの条件によって1を返すことになります。
結果としてfactional(3)は3 * 2 * 1 * 1を返すことになり、求めたい答え3! = 6を得ることができます。
再帰関数のポイント
再帰関数を作る際には、必ず処理を終わらせる条件が必要になります。このような条件はベースケースと呼ばれます。
もしベースケースが設定してないと再帰関数は無限ループになってしまいます。無限ループを避けるためにもベースケースは必須です。今回の階乗計算コードでは、「n = 0」の場合がベースケースとなっています。
また**ベースケースにたどり着けるような処理を構築することも重要です。**ベースケースを用意しても、そのベースケースにたどり着かなければ、結局処理が終わりません。
例えば以下のコードだと無限ループになってしまいます。
def factorial(n)
if n == 0.5
1
else
n * factorial(n - 1)
end
end
ifの条件が小数点になっています。nは自然数なので、nが小数になるケースは起こりません。このような例ではベースケースにたどり着けません。
なぜ再帰関数を学ぶのか
ループ処理を再帰関数で書けるようになると、プログラミングの幅が広がります。また深さ優先探索のようなアルゴリズムを実装する際にも再帰関数の考え方が重要（らしいです。まだ勉強中）です。
今回の階乗計算のような簡単な例だと、むしろ普通のループで実装したほうがわかりやすいように感じてしまいますが、深さ優先探索のようなアルゴリズムを実装するときには再帰関数を使うことでシンプルなコードで実装できるのだと思います。