この記事の対象者
こんな方におすすめ
・再帰関数ってどう処理が走るかイメージが湧きづらい人
再帰関数ってなに？
まずは、今回理解する再帰関数について説明します。
こちらについて調べると、下記のような説明がよくされています。
プログラム内で関数が自分自身を呼び出す仕組みを持つ関数のこと。大きな問題を小さな問題に分割して解く際に利用され、終了条件（ベースケース）を設定することで、階乗やツリー構造の探索など複雑な処理を簡潔に記述できる。
分かるようで、分からないような・・・。
百聞は一見にしかずということで、実際にサンプルコードを見てみましょう。
サンプルコード
function sumTo($n)
{
if ($n === 1) {
return 1;
}
// 再帰呼び出し
return $n + sumTo($n - 1);
}
//実行
echo sumTo(3);
//実行結果 6
再帰関数で調べるとよく見る、1からnまでの総和を求めるプログラムです。
初めて、再帰関数を見た時に、「あれっ？分かるようで分からない...。自分で自分を呼ぶってどういうことだ？？」となったので、今回は、絵でどのような処理がされているか理解してみます。
絵で理解してみよう
$n = 3の処理
まず、最初に$n = 3のときの処理から始めましょう。
//ここは条件に合わないので実行されない
// if ($n === 1) {
// return 1;
// }
// 再帰呼び出し
return 3 + sumTo(3 - 1);
$n = 3なので、最初のif文分岐には入りません。
そして、次の行
return 3 + sumTo(3-1);
これが実行されます。
一旦ここまでを絵で描くとこのような感じです。
ここで、sumToメソッドが呼ばれたので次の処理についても見てみましょう。
$n = 2の処理
先ほど、
sumTo(3-1)
この処理が呼ばれたので、次は$n = 2のときの処理を追っていきましょう。
実行されるプログラムは、
//ここは条件に合わないので実行されない
// if ($n === 1) {
// return 1;
// }
// 再帰呼び出し
return 2 + sumTo(2 - 1);
$n = 2なので、ここも最初のif文分岐には入りません。
そして、次の行
return 2 + sumTo(2-1);
これが実行されます。
ここまでを絵に描くとこのような感じです。
では、最後$n = 1のときの処理についても追ってみましょう。
$n = 1の処理
実行されるプログラムは、
//今回はこちらの処理が実行される
if ($n === 1) {
return 1;
}
// 再帰呼び出し
//return 2 + sumTo(2 - 1);
$n = 1なので、今回はifの分岐に入ります。
そして、
return 1;
このreturnが実行されます。
ここまでを絵で描くとこうなります。
sumTo(1)の実行結果が1となりましたね。
では、sumTo(2)の実行結果にも値を代入しましょう。
sumTo(2 -1);の結果が1になるので、sumTo(2)の結果が2 + 1 となります。
次に、sumTo(3)にも代入していきましょう。
sumTo(2)の結果が3だと分かったので、代入します。
絵で描くとこのようになり、sumTo(3)の結果が3 + 3の6であることが分かりました。
まとめ
再帰関数は、コードだけで見ると「あれっ？この処理の流れってどうなってるんだっけ？？」となりがちな概念ですが、絵で理解することで処理の流れが分かりやすくなったことが分かりました。
この絵で理解する方法は再帰関数以外にも有効だなと感じたので、処理の流れが分からなくなったときは、今後もやってみようと思います。