応用情報技術者試験令和7年春午前問7 解説付き過去問

問題

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

if n＝0 then return 0 else return n×fact(n－1)

if n＝0 then return 0 else return n×fact(n＋1)

if n＝0 then return 1 else return n×fact(n－1)

if n＝0 then return 1 else return n×fact(n＋1)

この問題は、非負の整数nに対する階乗の計算を再帰的に定義する方法について問うものです。階乗の計算は、数学やアルゴリズムの分野で頻繁に使用される重要な概念です。

階乗の基本的な定義
階乗は、1からその数までのすべての整数の積で表されます。例えば、5の階乗（5!）は 1×2×3×4×5 = 120 です。特に、0の階乗は1と定義されています。
再帰的な階乗の定義
階乗を再帰的に定義する場合、基底ケースとしてn=0のときの値を定め、それ以外の場合にはn×fact(n-1)として自己参照的に定義します。この再帰的なアプローチは、小さい問題へと問題を分割し、それを解決することで全体の解を構築します。n=0のとき1を返すことで、再帰の終了条件として機能し、正確な計算が可能になります。
誤った再帰定義の例
選択肢で提示された他の定義、例えば「if n＝0 then return 0 else return n×fact(n－1)」では、n=0のときに0を返してしまい、これは階乗の定義に反します。また、「if n＝0 then return 1 else return n×fact(n＋1)」のように、n+1を用いる定義は再帰が無限に続く可能性があり、実用的ではありません。

したがって、「if n＝0 then return 1 else return n×fact(n－1)」が正しい再帰的定義です。これは0の階乗を1と正しく定義し、それ以外のnでn-1の階乗にnを掛けることで、階乗を正確に計算します。