再帰呼出しとは？

再帰呼出しの意味

手続きが自分自身を呼び出す書き方。問題をより小さい同じ形の問題に分解して解く場合に自然に書ける。呼出しごとに引数や戻り先がスタックへ積まれるため、終了条件（これ以上分解しない場合）が必ず要る。

再帰呼出しの具体例

階乗を求める手続きは「n が1以下なら1を返し、そうでなければ n×階乗(n−1) を返す」と書ける。階乗(4) は 4×3×2×1 と展開され、最も内側の呼出しが戻り始めてから順に掛け算が確定していく。

再帰呼出しは試験でどう引っ掛けられる？

終了条件を書き忘れると呼出しが無限に積まれ、スタック領域を使い切って異常終了する（スタックオーバフロー）。また再帰は必ずしも高速ではなく、呼出しのオーバヘッドの分だけ反復より遅いことが多い。

再帰呼出しと関連する用語

• スタック
• 再入可能
• クイックソート

再帰呼出しが出た過去問

• fact(n)は、非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。

  正解：if n=0 then return 1 else return n×fact(n-1)

  要点：階乗の再帰は0!=1を基底にn×fact(n-1)

  階乗は0!=1を出発点として、n!=n×(n-1)!と再帰的に定義される。したがって再帰の基底部ではn=0のときに1を返し、それ以外はnと引数を1減らした再帰呼出しの積を返す形が正しい。

  出典：平成29年度 秋期 応用情報技術者試験 午前 問7（IPA）

• 再帰的な処理を実現するためには、再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要がある。そのための記憶管理方式はどれか。

  正解：LIFO

  要点：再帰の状態退避はLIFO（スタック）で管理する

  再帰呼出しでは、呼び出した順序と逆の順序で復帰するため、最後に退避した情報を最初に取り出す必要がある。この後入れ先出しの性質をもつ記憶管理方式がLIFOであり、スタックとして実装される。復帰アドレスやレジスタの内容はスタックフレームとして積み上げられる。

  出典：平成30年度 春期 応用情報技術者試験 午前 問8（IPA）

• fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。

  正解：if n=0 then return 1 else return n×fact(n-1)

  要点：階乗の再帰は0!=1を基底に、n×fact(n-1)で引数を減らす

  階乗の再帰的定義は、基底部で0の階乗を1とし、再帰部でnと「n-1の階乗」の積を返す形になる。基底部を0と置くと積が常に0になってしまうため、返す値は1でなければならない。また再帰呼出しの引数はn-1と減らさないと基底部に到達せず、無限再帰になる。

  出典：令和7年度 春期 応用情報技術者試験 午前 問7（IPA）