再帰関数とは、自身を直接または間接的に呼び出す関数です。この呼び出しはスタック構造に基づき、関数が新たなスコープを積み重ねながら進み、終了条件（ベースケース）に到達すると、積まれた各呼び出し層が逆順に復帰していきます。

再帰の正しく動作するためには、以下の3要素が不可欠です：

• ベースケース（終了条件）：再帰を停止させる明確な条件
• 再帰ステップ：問題をより小さな同一構造のサブ問題へ分解する処理
• 状態の変化：毎回の呼び出しでベースケースへ近づくように引数を更新

以下は、再帰の進行・復帰の両フェーズを可視化する改良版サンプルです：

<?php
function traceRecursion($depth, $maxDepth = 4) {
    // 【進行フェーズ】：深さを表示し、再帰呼び出し前に処理
    echo "→ 階層 {$depth}：開始\n";
    
    if ($depth < $maxDepth) {
        traceRecursion($depth + 1, $maxDepth);
    } else {
        echo "✓ 最深層 ({$depth})：終了条件に到達\n";
    }
    
    // 【復帰フェーズ】：呼び出し元へ戻った直後に実行
    echo "← 階層 {$depth}：復帰\n";
}

traceRecursion(0);
?>

出力結果：

→ 階層 0：開始  
→ 階層 1：開始  
→ 階層 2：開始  
→ 階層 3：開始  
→ 階層 4：開始  
✓ 最深層 (4)：終了条件に到達  
← 階層 4：復帰  
← 階層 3：復帰  
← 階層 2：復帰  
← 階層 1：復帰  
← 階層 0：復帰

この出力から分かる通り、関数はまず「→」で示される下降過程でスタックに積まれ、ベースケースで停止した後、「←」で示される上昇過程で順次復帰します。各層の復帰タイミングで、呼び出し直後のコード（例ではecho "← ..."）が実行されます。

もう一つの具体例として、入れ子関数による制御フローを示します：

<?php
function outer($x) {
    echo "[OUTER] 入力: {$x}\n";
    middle($x - 1);
    echo "[OUTER] 復帰: {$x}\n";
}

function middle($y) {
    echo "[MIDDLE] 入力: {$y}\n";
    inner($y - 1);
    echo "[MIDDLE] 復帰: {$y}\n";
}

function inner($z) {
    echo "[INNER] 入力: {$z}\n";
    // 終端：これ以上呼び出さない
}

outer(3);
?>

実行結果：

[OUTER] 入力: 3  
[MIDDLE] 入力: 2  
[INNER] 入力: 1  
[MIDDLE] 復帰: 2  
[OUTER] 復帰: 3

この例では、outer → middle → inner の順で関数が呼び出され、inner が終了すると middle の残り部分が実行され、さらにその完了で outer の残りが実行されます。これは再帰ではなく単なる関数の連鎖呼び出しですが、スタックによるLIFO（Last In, First Out）の制御フローを理解する上で有効です。