Zenn
😺

再帰関数がわからない初心者向けの覚書き スタックフレームを中心に

2024/05/28に公開
再帰関数
tech

AtCoderで出てきたので再帰関数について学んでいます。

再帰関数のワケの分からなさの一因は、関数実行の裏にスタックフレームという存在があり、その動きが分かりにくいためではないかと気づきました。

そこで、この記事ではスタックフレームの動きを中心に、再帰関数での具体的な流れを追っていき再帰関数内で値が渡されていく様子をみてみたいと思います。

再帰関数をまなぶ

再帰関数自体の理解には良い記事がたくさんあります。

うさぎでもわかる再帰関数のいろは
↑こちらは図入りで練習問題もあり理解しやすいのでオススメです。

スタックフレームの動作

  1. 各関数の呼び出しのたびに新しいスタックフレームが作成される
  2. 関数が値を返すと(return)そのスタックフレームは破棄される

つまり、関数が値を返した時点で、そのスタックフレームは基本的にメモリから消えてしまいます。

一方、return等で関数が終了していない場合はスタックフレームは保持され続けます。ネストされた制御構造で多重ループ処理を行う場合等がこれにあたり、この場合はスタックフレームが連続して作成されます。

これはifやfor文でも同じです。

再帰関数の流れと出力

スタックフレームの動きがわかりやすいように処理の途中でechoにて関数の値を確認していきます。

※PHPerなのでPHPで書きます。他の言語の方はChatGPTに放り込めば翻訳してくれます。

<?php

function factrial($n)
{
  if ($n == 0) {
    return 1;
  } else {
    $result = $n * factrial($n - 1);
    echo "factorial($n) = $result" . PHP_EOL;
    return $result;
  }
}

echo factrial(3) . PHP_EOL;

具体的な流れは次のようになります：

  1. factorial(3) を呼び出す

    • 3 * factorial(2) を計算します。
    • スタックフレームが作成されます。

  2. factorial(2) を呼び出す

    • 2 * factorial(1) を計算します。
    • スタックフレームが作成されます。

  3. factorial(1) を呼び出す

    • 1 * factorial(0) を計算します。
    • スタックフレームが作成されます。

  4. factorial(0) を呼び出す

    • 基本ケースに達し、1 を返します。
    • factorial(1) のスタックフレームが 1 を受け取ります。

factorial(1) のスタックフレームが 1 を受け取ります。
これがポイントで、ここでやっと値を受け取ったことで処理できずにいたfactorial($n)達の処理を開始することができます。
一番最近呼び出したfactorial($n)にもどって順番に処理を行っていきます。
※だから再帰と名付けられたのですね！

  1. factorial(1) の計算

    • 1 * 1 を計算し、1 を返します。
    • echo "factorial(1) = 1\n"; が出力されます。

  2. factorial(2) の計算

    • 2 * 1 を計算し、2 を返します。
    • echo "factorial(2) = 2\n"; が出力されます。

  3. factorial(3) の計算

    • 3 * 2 を計算し、6 を返します。
    • echo "factorial(3) = 6\n"; が出力されます。

最終的な出力は以下のようになります：

factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
6

スタックフレームの破棄

各関数呼び出しが完了し、値を返した時点で、そのスタックフレームは破棄されます。そのため、factorial(2) のスタックフレームは factorial(3) に結果を返した後に破棄されます。

まとめ

スタックフレームの動きを理解すれば再帰関数を理解しやすくなります。
ぜひこの記事を活用してください。

Discussion