再帰呼出しとは？さいきよびだし
再帰呼出しとは、手続きが自分自身を呼び出す書き方。問題を同じ形のより小さな問題へ分解して解く場合に自然に記述でき、呼出しのたびに引数と戻り先がスタックへ積まれるため、これ以上分解しない終了条件を必ず用意する必要がある。
最終更新：2026-10-06
この語が出る過去問を解く →背景
木構造の探索や分割統治法では、処理すべき深さや個数が実行時まで決まらない。これを繰返しで書こうとすると、途中の状態を自分でスタックへ積み直す処理をコードに書き足すことになる。再帰呼出しは、その積み直しを言語処理系のコールスタックに任せる書き方であり、アルゴリズムの構造をそのまま写せる。擬似言語の追跡問題として出題される。
具体例
階乗は「nが1以下なら1、そうでなければn×階乗(n−1)」と書け、階乗(4)は最も内側の呼出しが戻り始めてから4×3×2×1と順に確定する。クイックソートや二分探索木の走査も同じ形で、分割統治法の実装をそのまま再帰として表現できる。
試験での引っ掛け
終了条件を書き忘れると呼出しが積まれ続け、スタック領域を使い切って異常終了する（スタックオーバフロー）。再帰は必ずしも高速ではなく、呼出しのオーバヘッドのぶん反復より遅いことが多い。素朴な再帰でフィボナッチ数を求めると同じ引数が何度も再計算され、計算量が指数的に膨らむ点も問われる。
関連用語
出た過去問
出典：平成29年度 秋期 応用情報技術者試験 午前 問7（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×(n-1)!と再帰的に定義される。したがって再帰の基底部ではn=0のときに1を返し、それ以外はnと引数を1減らした再帰呼出しの積を返す形が正しい。
出典：平成30年度 春期 応用情報技術者試験 午前 問8（IPA）解説で登場
再帰的な処理を実現するためには、再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要がある。そのための記憶管理方式はどれか。
正解：LIFO
要点：再帰の状態退避はLIFO（スタック）で管理する
再帰呼出しでは、呼び出した順序と逆の順序で復帰するため、最後に退避した情報を最初に取り出す必要がある。この後入れ先出しの性質をもつ記憶管理方式がLIFOであり、スタックとして実装される。復帰アドレスやレジスタの内容はスタックフレームとして積み上げられる。
出典：令和7年度 春期 応用情報技術者試験 午前 問7（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と減らさないと基底部に到達せず、無限再帰になる。
出典・参考
公式シラバスの1 基礎理論 ＞ 4. プログラム言語 ＞ (2) プログラム言語の制御構造に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。