再帰関数を理解できるように詳しくまとめる

再帰関数についてまとめたいと思います。

再帰関数とは

関数の中で、その関数自身を呼ぶような関数のことを再帰関数といいます。

再帰関数の例としてよくあげられるのは、階乗するようなケースです。
$3!$などの計算のことです。

$3!$のケースを考えると、
$3! = 3 × 2 × 1$
という計算になりますが、この乗算する処理を自身で実行してしまおう
というのが、再帰関数になります。

階乗処理を例とした再帰関数の実装

階乗処理をベースに再帰関数を書いてみたいと思います。

引数に階乗したい数値を入れ、
その階乗した値を返す関数を再帰関数で考えてみます。

factorial(int n ){
  if(n == 1) return 1;
  return n * factorial(n - 1)
}

再帰関数の処理を図式化する

関数だけだと、処理を想像することが難しいので、
図式化したいと思います。

階乗したい数値を4として、factorial関数に代入する様子をみてみます。

再帰関数1回目の処理

factorialに4を代入します。

return 4 × factorial(4 - 1)

ここで、factorial(4 - 1)として自身を呼び出しています。
return処理は行われず、factorial(4 - 1)関数が先に呼ばれます。

再帰関数2回目の処理

factorial(4 - 1)を呼びます。

return 3 × factorial(3 - 1)

factorial(3 - 1)を呼びします。
まだreturnはしていません。

再帰関数3回目の処理

factorial(3 - 1)を呼びます。

return 2 × factorial(2 - 1)

factorial(2 - 1)を呼び出します。
次から展開が変わります。。。

再帰関数4回目の処理

factorial(2 - 1)を呼び出します。

if(n == 1) return 1;

nが1なので、ようやくここで、1をreturnします。
factorial(2 - 1)を呼び出した、3回目の処理にもどります。

factorial(3 - 1)の処理

factorial(2 - 1)の処理結果として1が返ってきたので、 factorial(2 - 1)の処理を呼び出していた、
factorial(3 - 1)のreturnが以下のように返るようになります。

return 2 × 1

次に、factorial(3 - 1)を呼び出していた、
factorial(4 - 1)のreturn処理が行われることになります。

factorial(4 - 1)の処理

factorial(3 - 1)が2 × 1と返ってきたため、 factorial(4 - 1)のreturn部分の処理が行われます。

return 3 × factorial(3 - 1)

つまり

return 3 × 2 × 1

がfactorial(4 - 1)のreturn値になります。
factorial(4 - 1)を呼んだfactorial(4)のreturn値が返ることになります。

factorial(4)の処理

いよいよ、factorial(4)の処理が終わります。

return 4 × factorial(4 - 1)

つまり

return 4 × 3 × 2 × 1

が、最終的な値として、返ってくることになります。