コードを見ながら理解する「入れ子構造」と「再起関数」

実は私、プログラミングを学習する中で、入れ子構造と再起関数という言葉を何度も目にしてきましが、その度に理解するのを放り投げてきました。

実はそんな人多いのではないでしょうか？（多いですよね？…）

流石にそろそろ逃げてはいられないでしょうということで、これを機に入れ子構造と再起関数について理解を深めていきたいと思います。

入れ子構造って聞いたことあるけどよくわからない
再起ってどこで使うの？

入れ子構造を理解する

再起関数を理解するためには、「入れ子構造」を理解している必要があります。というのも、再起関数を使う場面は入れ子構造であることが多いからです。

入れ子構造とは、つまりネストのことです。

wikipediaによると

構造化プログラミングにおけるネスティング（英: Nesting）、ネスト、入れ子とは、プログラムの構造が再帰的に繰り返されて記述されること。このような構造をネスト構造（英: Nested structure）、入れ子構造と呼ぶ。
https://ja.wikipedia.org/wiki/%E3%83%8D%E3%82%B9%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0#%E3%83%AB%E3%83%BC%E3%83%97%E6%96%87%E3%81%AE%E3%83%8D%E3%82%B9%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0

となっています。

例えば以下のようにif文がネストしていても入れ子構造です。

if (条件式) {
 if (条件式) {
   if (条件式) {
...
   }
　}
}

マークアップ上では要素を囲んでネストさせた状態を入れ子と呼びます

<div>
  <p>文章</p>
  <ul>
    <li>リスト１</li>
    <li>リスト２</li>
  </ul>
</div>

これは配列にも当てはまります。

[1,2,[[3,4],5]]

それでは、この配列の各要素に対して変更を加えたい場合はどうすれば良いのでしょうか？

今回は各要素を２倍にするという処理を実行したいと思います。

普通の配列のようにforeach文を回してみます。

$array = [1,2,[[3,4],5]];
foreach ($array as &$value) {
  $value = $value * 2;
}
//実行結果
Fatal error: Uncaught TypeError: Unsupported operand types: array 
var_dump($array);

すると、実行結果はTypeError…

よく考えてみると怒られるのは当然です。

なぜなら、入れ子構造の配列は配列の中に配列が入っているのですから。

つまり、$value * 2の処理で$valueに配列が渡ってしまっているからです。

配列に2をかけることなどできませんから、怒られてしまっているというわけです。

再起関数を理解する

入れ子構造の配列の各要素に対してアプローチをしたい時にはどうしたら良いのでしょうか。

まず考えられるのは、ネストしている分foreach文を回すということでしょうか？

$array = [1,2,[[3,4],5]];
foreach ($array as &$kaisou1) {
    if (!is_numeric($kaisou1)){
        foreach ($kaisou1 as &$kaisou2) {
            if (!is_numeric($kaisou2)){
                foreach ($kaisou2 as &$kaisou3) {
                    $kaisou3 = $kaisou3 * 2;
                }
            }
            if (!is_numeric($kaisou2)) continue;
            $kaisou2 = $kaisou2 * 2;
        }   
    }
    if (!is_numeric($kaisou1)) continue;
  $kaisou1 = $kaisou1 * 2;
}
var_dump($array);

一応この方法で問題の配列は対応できそうです。

ただ、ものすごく読みにくい…

また、３階層以上入れ子になっている配列に対応できなかったりと汎用性は低そうです。

そこで登場するのが「再起関数」です。

再起関数は一言で言うと、「自分で自分を呼び出す関数」になります。

先程の問題を再起関数を使って表すと以下のようになります。

$array = [1,2,[[3,4],5]];
saiki($array);
function saiki(&$array) {
  foreach ($array as &$value) {
      if ($value == is_numeric($value)) {
          $value = $value * 2;
      } else {
　　　　　　//注目
          saiki($value);
      }
  }
}
var_dump($array);

再起関数を使うとだいぶスッキリしました。

注目したいのは9行目のsaiki($value)です。

ここで自分自身を呼び出していることがわかります。これが再起関数です。

実際どのように再起関数が呼ばれているのか追ってみます。

ポイントは再起関数を呼び出す(出さない)タイミングです。

foreach文の中をみてみると、まず初めに各要素に対して数値か否かの判定をしています。

数値なら2を掛けて、数値でなければ再起関数を呼び出しています。そして呼び出される引数に配列の要素を渡しています。

実際に処理されている順番を表すと以下のようになります。