目標
アルゴリズムを利用した方法で再帰関数がよく使われるので練習して使えるようにする
そもそも再帰関数とは？
アルゴリズムなどを記述するときに、自分自身を引用する形で定義することを再帰的定義といい
自分自身を呼び出す関数のことを再帰関数といいます。
再帰関数の基本的なルールは2つです。
1：自分自身の関数を用いて、問題を少し簡単にするための計算式をたてる
2：簡単なパターンの場合の答えを用意する
階乗を求める関数factorialを用いて問題を解いてみましょう。
階乗(factorial)を求めるメソッド
def factorial(n)
if n <= 0
#0! = 1なので1を返す
return 1
else
# 動作確認用
p n
#ここでfactorial自身を呼び出す
return n * factorial(n-1)
end
end
p factorial(5) #1205! = 120なので問題ないですね。
p nで動きを確認すると・・・
5
4
3
2
1↑のようにnの値が変化していることを確認できます。
p n * fact(n-1) で動きを確認すると・・・
1
2
6
24
120↑のように出力されることが確認されます。
これは再帰関数を使わない、each,times,whileなどのようなループとは挙動が違い、
初めて使う場合はなぜこのようになるのか混乱してしまいます。
そこでpコマンドなどで処理の流れを見ることでどうなっているのか確認します。
p “#{n} * #{fact(n-1)}” で処理を確認してみると・・・
"1 * 1"
"2 * 1 * 1"
"3 * 2 * 1 * 1"
"4 * 3 * 2 * 1 * 1"
"5 * 4 * 3 * 2 * 1 * 1"
"5 * 4 * 3 * 2 * 1 * 1"↑のように計算していることがわかりますね。
実際はこのように動いているようです。
1：factorial(5)はfactorial(4) × 5 を返すことになっているので、関数factorial(4)を呼び出します。
2：factorial(4)はfactorial(3) × 4 を返すことになっているので、関数factorial(3)を呼び出します。
3：factorial(3)はfactorial(2) × 3 を返すことになっているので、関数factorial(2)を呼び出します。
4：factorial(2)はfactorial(1) × 2 を返すことになっているので、関数factorial(1)を呼び出します。
5: factorial(1)はfactorial(0) × 1 を返すことになっているので、関数factorial(0)を呼び出します。
6：factorial(0)はN<=0の条件をみたすので1を返します。
7：factorial(1)はfactorial(0)の呼び出しが終わったので1 × 1 = 1を返します。
6：factorial(2)はfactorial(1)の呼び出しが終わったので2 × 1 × 1 = 2を返します。
7：factorial(3)はfactorial(1)の呼び出しが終わったので3 × 2 × 1 × 1= 6を返します。
8：factorial(4)はfactorial(1)の呼び出しが終わったので4 × 3 × 2 × 1 × 1 = 24を返します。
9：factorial(5)はfactorial(1)の呼び出しが終わったので5 × 4 × 3 × 2 × 1 × 1 = 120を返しますこれにより5～9の部分が出力されたので1,2,6,24,120というように出力されました。