ちょうどさっき、再帰関数の説明を新人エンジニアにしたら、アドリブの割にそれっぽかったのでメモ。
再帰関数（さいきかんすう）とは？
再帰関数とは、自分で自分を呼んでいる関数である。
これだけ書くと頭おかしい人しかイメージ出来ないと思うので、とりあえずプログラムで説明する。
どの言語でも再帰関数の考え自体は同じなので、ここではPHPで書いてみる。
// saiki:再帰処理
function saiki($hikisu) {
echo $hikisu;
if ($hikisu > 0) {
saiki($hikisu - 1);
}
}赤い部分にご注目。
自分で自分を呼んでいるということがお分かりだろうか？
（問１）出力結果はどうなるでしょう？
ここで問題。
この関数を以下のように使ってみると、出力結果はどうなるでしょうか？
saiki(5);（問１）答え
問１の出力結果は以下の通り。
543210
関数を呼んだのは1回だけ。
ループ処理を使ってるわけでもない。
それなのに「5」という引数に対して、上記のように出力された。
これが再帰関数の動きだが、プログラムの進行がイメージできるだろうか？
学生時代、数学が得意だった人はイメージしやすいかもしれない。
式の置き換えと同じように考えてみると、上記の再帰関数は以下のようなプログラムになる。
（あくまでイメージなので、そのまま動くソースではない）
saiki(5) {
echo 5; // -> 出力結果：5
if (5 > 0) {
saiki(5 - 1) {
echo 4; // -> 出力結果：54
if (4 > 0) {
saiki(4 - 1) {
echo 3; // -> 出力結果：543
if (3 > 0) {
saiki(3 - 1) {
echo 2; // -> 出力結果：5432
if (2 > 0) {
saiki(2 - 1) {
echo 1; // -> 出力結果：54321
if (1 > 0) {
saiki(1 - 1) {
echo 0; // -> 出力結果：543210
if (0 > 0) {
// ここには入らない
}
}
}
}
}
}
}
}
}
}
}
}saiki(5);と呼び出された場合、プログラムは上記のように動いている。
ここで注目して欲しいのが、青字の部分。
青字の部分は、再帰処理の開始と終了を表している。
再帰処理を考えるうえで大事なことは終了条件であり、確実に終了する条件でないと、合わせ鏡のような無限ループが出来上がるので注意！
（問２）出力結果はどうなるでしょう？
以下のように再帰関数が変わりました。
// saiki:再帰処理
function saiki($hikisu) {
// ここから、
if ($hikisu > 0) {
saiki($hikisu - 1);
}
echo $hikisu; // ここに移動
}コメントにある通り、echoの位置が変わっています。
この場合、以下のプログラムの出力結果はどうなるでしょうか？
saiki(5);（問２）答え
問２の出力結果は以下の通り。
012345
前回と順番が逆になった。なぜか？
ここでも同じようにプログラムを置き換えてみる。
saiki(5) {
if (5 > 0) {
saiki(5 - 1) {
if (4 > 0) {
saiki(4 - 1) {
if (3 > 0) {
saiki(3 - 1) {
if (2 > 0) {
saiki(2 - 1) {
if (1 > 0) {
saiki(1 - 1) {
if (0 > 0) {
// ここには入らない
}
echo 0; // -> 出力結果：0
}
}
echo 1; // -> 出力結果：01
}
}
echo 2; // -> 出力結果：012
}
}
echo 3; // -> 出力結果：0123
}
}
echo 4; // -> 出力結果：01234
}
}
echo 5; // -> 出力結果：012345
}問２のプログラムの場合、このように動く。
ここで伝えたいのは、再帰関数は最後に呼ばれたものから終了するということである。
上記２つのプログラムの例をしっかりと理解できれば、再帰関数は怖くない！
再帰関数の使いどころ
どういうものかは分かったけど、使い道が分かんない。
という人のために、使いどころをご紹介。
掲示板の返信機能を再帰関数で
Facebookのコメント欄など、返信機能のあるシステムをイメージして欲しい。
これらは、元になる記事やコメントがあって、それに対して返信され、さらにその返信に対して返信、さらにその返信の返信に対して返信…といった風に、無限に返信が繰り返される。
こういった処理に再帰関数は適している。
以下にサンプルソースを書く。
【テーブル構造】
id: コメントID
replyId: 返信元コメントID
comment: コメント本文
【プログラム】
// 返信取得処理
function getReply($commentId) {
// exeSQL:引数のSQL文を実行し、結果を取得する関数。取得できなければ""を返す。
$replies = exeSQL("SELECT * FROM articles WHERE replyId == $commentId");
if ($replies != "") {
foreach ($replies as $reply) {
echo '<div class="reply">' . $reply["comment"] . '</div>';
getReply($reply["id"]);
}
}
}
※exeSQLは標準関数ではなく、ユーザー定義関数です
あくまで例として適当に書いたので、雰囲気だけ感じて欲しい。
このように再帰関数を使うと、無限に続くかもしれない返信の嵐も、スマートに処理することが出来る。
まとめ
さいごに再帰関数についてまとめる。
- 再帰関数は自分で自分を呼ぶ関数
- 大事なのは確実に終わることができる終了条件
- 処理は最後に呼ばれた関数から終わる
あとは実践あるのみ！どんどん再帰関数を使ってみよう！
