プログラマー初心者の壁「再帰処理」を実装しながら理解してみた

こんにちは。決済認証システム開発事業部の松浦と申します。現在Go言語を用いたAPIサーバーの開発を担当しています。

再帰というものについての記事を書きたいと思います。再帰という考え方はプログラミングに適用できますが、言語学・論理学・数学・計算機科学など幅広い分野で使われているようです。休みの日などにプログラミング関連の本やwebの情報を読んだり、見たりすることが多く、再帰がどうこうという話が色々な所で出てきてなかなか理解できなかったのが、この記事を書こうと思ったきっかけになります。

まず、プログラミングの文脈における再帰(Recursion)の定義は以下のようになります。

再帰（再帰呼び出し）の定義

ある手続きの中で自分自身を呼び出すこと

また、再帰という考え方に慣れておくと以下のようなメリットがあると思います。

再帰を使ったプログラミングテクニックはフレームワークやライブラリで多く使われているため、それらの実装を理解するのに役立つ
再帰的な構造を持つデータ構造（グラフ、木、入れ子になった配列など）を走査するアルゴリズムを自然に実装できるようになる

再帰処理の基本テンプレート

再帰を使う関数のテンプレートを疑似コードで表すと以下の通りになります。

recFunc(引数){
    if(ベースケース){
        return ベースケースに対応する値;
    }

    // 再帰的に自分自身を呼び出す
    result = recFunc(次の引数);

    // 答えを返す
    return result;
}

総和を計算する関数の実装例

上の定義を使って1からNまでの総和を計算するPHPの関数を書くと以下のようになります。

<?php
function summation(int $number) {
    // ベースケース
    if ($number === 0){
        return 0;
    }

    // 再帰的に自分自身を呼び出す
    $result = $number + summation($number - 1);

    // 答えを返す
    return $result;
}

echo summation(10);
?>

// 実行結果
55

ここでのポイントは、再帰呼び出しの呼び出し先が徐々にベースケース（終了条件）に向かっていくように実装することです。上の例だと、再帰呼び出しの箇所がsummation($number-1)となっているので、summationメソッドの引数$numberが徐々に0（ベースケース）に向かっていきますが、summation($number+1)とすると、$numberが増えていくことになり上手くいきません。

多次元配列から再帰処理で文字列の要素を取り出す例

最後に再帰的な構造を持つ配列から、文字列の要素の一覧を取り出すPHPの関数を書いてみます。

<?php
// 処理対象の再帰的な構造を持つ配列
$inputArray = ['a', 1 , ['b', 2, ['c', 3]]];

function getStrFromArray($arg) {
    $results = [];

    if (is_string($arg)){
        $results[] = $arg;
    } elseif(is_array($arg)) {
        foreach($arg as $value){
            $results = array_merge($results, getStrFromArray($value));
        }
    }
    
    return $results;
}

var_dump(getStrFromArray($inputArray));
?>

// 実行結果
array(3) {
  [0]=>
  string(1) "a"
  [1]=>
  string(1) "b"
  [2]=>
  string(1) "c"
}

この実装におけるベースケースは$argがStringかどうか判定している部分になります。

以上になります。再帰に興味が湧いた方がもしいらっしゃれば、とても面白いトピックですのでぜひ色々と調べてみてください!