再帰とは？

再帰の意味

手続きが自分自身を呼び出す仕組み。「終了条件（基底）」と「自分自身をより小さい問題で呼ぶ部分」の2つで構成する。

再帰の具体例

階乗は「0!＝1」「n!＝n×(n−1)!」。ユークリッドの互除法は「gcd(a, 0)＝a」「gcd(a, b)＝gcd(b, a mod b)」。

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

再帰呼出しは実行中の状態をスタックに積むため、深さが大きいとスタックオーバフローを起こす。また、同じプログラムを複数から同時に呼べる性質は「再入可能（リエントラント）」であって再帰とは別概念。

再帰と関連する用語

• スタック
• 分割統治法

再帰が出た過去問

• 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）