再帰関数を使って階乗を求めるメソッドを作成する(Ruby)

初めに

アルゴリズムを利用した方法で再帰関数がよく使われるので
階乗を求める再帰関数を作成して理解を深めます。

そもそも再帰関数とは？

アルゴリズムなどを記述するときに、
自分自身を引用する形で定義することを再帰的定義といい
自分自身を呼び出す関数のことを再帰関数といいます。

再帰関数で注意すること

1：自分自身の関数を用いて、問題を少し簡単にするための計算式をたてます

2：無限ループにならないようにベースケースを作成します。

階乗を求める関数factorialを作成してみましょう。

階乗(factorial)を求めるメソッド

ruby

def factorial(n) 
  if n <= 0  
  # 0! = 1 なので1を返します。(※ここがベースケース)
     return 1
  else
   #※1：動作確認用
   p n
   #※2:ここでfactorial自身を呼び出します
   return n * factorial( n - 1 ) 
  end
end
# 計算結果を出力(120が出力される)
p factorial(5) 

5! = 120なので問題ないですね。

※1の動作確認用のp nの部分で動きを確認すると・・・

5
4
3
2
1

↑のようにnの値が変化していることを確認できます。

※2の部分を p n * factorial( n - 1 ) に変更して動きを確認すると・・・

1
2
6
24
120

↑のように出力されることが確認できます。
これは再帰関数を使わない、each,times,whileなどのようなループとは挙動が違い、初めて使う場合はなぜこのようになるのか混乱してしまいます。

そこでpコマンドなどで処理の流れを見ることでどうなっているのか確認します。

※2の部分を p "#{n} * #{factorial( 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を返します。
8：factorial(2)はfactorial(1)の呼び出しが終わったので2 × 1 × 1 = 2を返します。
9：factorial(3)はfactorial(1)の呼び出しが終わったので3 × 2 × 1 × 1= 6を返します。
10：factorial(4)はfactorial(1)の呼び出しが終わったので4 × 3 × 2 × 1 × 1 = 24を返します。
11：factorial(5)はfactorial(1)の呼び出しが終わったので5 × 4 × 3 × 2 × 1 × 1 = 120を返します。

終わりに

再帰関数の処理の流れを見ることでどのように動いているか理解を深めることができました。