再帰関数を説明する時、こんな感じで

PHPで再帰関数を教える男と教わる女

ちょうどさっき、再帰関数の説明を新人エンジニアにしたら、アドリブの割にそれっぽかったのでメモ。

再帰関数(さいきかんすう)とは?

再帰関数とは、自分で自分を呼んでいる関数である。

再帰関数 = I love me ?

これだけ書くと頭おかしい人しかイメージ出来ないと思うので、とりあえずプログラムで説明する。

どの言語でも再帰関数の考え自体は同じなので、ここではPHPで書いてみる。

// saiki:再帰処理
function saiki($hikisu) {
  echo $hikisu;
  if ($hikisu > 0) {
    saiki($hikisu - 1);
  }
}

赤い部分にご注目。
自分で自分を呼んでいるということがお分かりだろうか?

(問1)出力結果はどうなるでしょう?

ここで問題。

この関数を以下のように使ってみると、出力結果はどうなるでしょうか?

saiki(5);

(問1)答え

問1の出力結果は以下の通り。

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);と呼び出された場合、プログラムは上記のように動いている。
ここで注目して欲しいのが、青字の部分。

青字の部分は、再帰処理の開始と終了を表している。

再帰処理を考えるうえで大事なことは終了条件であり、確実に終了する条件でないと、合わせ鏡のような無限ループが出来上がるので注意!

(問2)出力結果はどうなるでしょう?

以下のように再帰関数が変わりました。

// saiki:再帰処理
function saiki($hikisu) {
  // ここから、
  if ($hikisu > 0) {
    saiki($hikisu - 1);
  }
  echo $hikisu; // ここに移動
}

コメントにある通り、echoの位置が変わっています。
この場合、以下のプログラムの出力結果はどうなるでしょうか?

saiki(5);

(問2)答え

問2の出力結果は以下の通り。

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
}

問2のプログラムの場合、このように動く。

ここで伝えたいのは、再帰関数は最後に呼ばれたものから終了するということである。

上記2つのプログラムの例をしっかりと理解できれば、再帰関数は怖くない!

再帰関数の使いどころ

どういうものかは分かったけど、使い道が分かんない。

という人のために、使いどころをご紹介。

掲示板の返信機能を再帰関数で

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は標準関数ではなく、ユーザー定義関数です

あくまで例として適当に書いたので、雰囲気だけ感じて欲しい。

このように再帰関数を使うと、無限に続くかもしれない返信の嵐も、スマートに処理することが出来る。

まとめ

さいごに再帰関数についてまとめる。

  • 再帰関数は自分で自分を呼ぶ関数
  • 大事なのは確実に終わることができる終了条件
  • 処理は最後に呼ばれた関数から終わる

あとは実践あるのみ!どんどん再帰関数を使ってみよう!

投稿者: Output48

中学生の時に初めてHTMLに触れてからホームページ制作を独学で始める。 ベンチャー企業の営業、大手企業のPG・SEを経て、独立。 現在はとある企業のCTOと、変な名前の会社の社長をしてる。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください