平成25年度春期 データベーススペシャリスト 午前Ⅰ 問2

再帰定義を読む一つの視点

再帰関数の定義を確認するときは、各部分がどの条件に依存し、どこで確認を終えられる構成になっているかという一点に注目して、全体のつながりを落ち着いて読み取ります。表現の細部だけで判断しないことも大切です。

この問題で問われていること

選択肢を比べる前に、定義の各要素が互いにどのような順序で参照され、確認が行き止まりにならないかを、問題文の記述に沿って一つの流れとして確かめてください。まず依存関係に集中します。

視点

再帰的な定義を読む際は、個々の記号や文言を切り離して見るのではなく、前提となる条件と、それを受けて確認する部分の関係を一つの流れとして整理します。

確認ポイント

• 各要素が何を参照しているか確認する
• 参照の順序を一つの流れで追う
• 途中で確認できなくなる箇所がないか見る

正解

ウ

解説

階乗は0の階乗を1とし、正の整数nではnに一つ小さい整数の階乗を掛けて定義します。したがって、停止条件と引数の減少がそろう再帰定義を選びます。

理由

階乗は0!=1を基礎とし、n>0ではn!=n×(n−1)!と定義されます。nが1ずつ減ることで、最終的に0に到達し、計算が停止します。この条件を満たす再帰定義が適切です。

比較

停止条件で0を返すと、1!=1×0が0になり、階乗の値になりません。また、再帰呼出しでnを増やす定義は0へ近づかず、正の整数から開始すると停止できません。

選択肢ア

これは不正解だよ。再帰呼出しの引数をn−1としている点は終了条件へ近づくため適切ですが、n＝0のときに0を返しています。例えば1の階乗は1×0となり、正しい階乗の値になりません。

選択肢イ

これは不正解だよ。n＝0のときに0を返すため、階乗の基本値である0!=1と一致しません。さらに、nが0でない場合にn＋1を渡すので、正の整数から始めると終了条件から遠ざかり、再帰が停止しません。

選択肢ウ（正解）

これは正解だよ。n＝0のときに1を返すので0!=1を満たし、nが0でないときはn−1を次の引数にします。例えばfact(3)は3×2×1×1となり、6を返して正しい階乗を計算できます。

選択肢エ

これは不正解だよ。n＝0のときに1を返すため基本値は正しいものの、再帰呼出しでn＋1を渡しています。正の整数から始めると引数が増え続けて0に到達せず、階乗の計算として停止しません。

学習のポイント

階乗の基本値と、再帰呼出しが終了条件へ近づく仕組みを理解しましょう。