テクノロジ系 / アルゴリズムとプログラミング
再帰
再帰は、処理の中で自分自身と同じ処理を呼び出して問題を小さくしていく考え方です。
もう少し詳しく
階乗、フィボナッチ数、木構造の探索などで使われます。必ず終了条件が必要で、終了条件がないと呼出しが止まらず、スタックを消費し続けます。問題を小さくして同じ形の処理に渡し、戻ってきた結果を組み合わせる流れを理解すると、疑似コードのトレースもしやすくなります。
試験での見方
例：n!を求める関数は、n=1なら1を返し、それ以外はn×(n-1)!を返します。4!なら4×3!、3!なら3×2!と呼び出しが続き、1!まで到達したあと、戻りながら結果を掛け合わせます。
再帰の問題では、終了条件、引数がどう小さくなるか、戻り値がどう合成されるかを順番に確認します。呼び出し順と戻り順が逆になる点に注意しましょう。