BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
再帰
同じ形の小さな問題へ分ける
再帰は、ある処理を定義する中で、その処理自身をより小さな対象などに対して呼び出す方法です。木構造の走査や分割統治法など、問題の中に同じ形の部分問題がある場合に自然に表現できます。自分を呼ぶことだけでなく、必ず終了する条件と、そこへ近づく変化が必要です。
階乗の例
def factorial(number):
if number < 0:
raise ValueError('number must be nonnegative')
if number == 0:
return 1
return number * factorial(number - 1)
result = factorial(4)
4の階乗を求めるには3の階乗を使い、さらに2、1、0へ進みます。0で1を返すところが基底条件です。呼出しが戻るときに、1、2、6、24と結果が組み立てられます。
呼出しと戻りを分ける
再帰の途中では、各呼出しが自分の引数や戻った後に行う処理を保持します。同じ変数名でも、全ての呼出しで一つの値を共有しているとは限りません。試験で結果を追うときは、呼び出していく順序と、戻って計算する順序を分けて記録すると理解しやすくなります。
深さと計算の重複
終了条件があっても、深さが大きすぎると呼出しスタックの容量を超える場合があります。また、同じ部分問題を何度も再計算する素朴な再帰は、処理量が急増することがあります。結果を記憶するメモ化や、繰返し処理への変更によって改善できる場合があります。短いコードであることと、効率がよいことは同じではありません。
試験で確認すること
基底条件、引数がどう変わるか、呼出しの前後で何を行うかを見ます。二つ以上の再帰呼出しがある場合は、深さだけでなく呼出しの総数を考えます。再帰と繰返しは多くの場合相互に表現できますが、状態を明示的なスタックに移す必要があることもあります。問題の構造が再帰的か、実行環境の制限に合うかを合わせて判断しましょう。
参考資料
内容確認日:2026-11-13