基本情報 平成28年度 秋期 問7：テクノロジ系に関する問題

答えは c「n × f(n-1)」 です。

階乗は「1からnまで全部かけ算」。

• 5! = 5 × 4 × 3 × 2 × 1

これを「今の数 × 1つ小さい数の階乗」と分解できます：

• 5! = 5 × 4!
• 4! = 4 × 3!
• ...
• 1! = 1 × 0! = 1

自分を呼び出す（小さい問題に置き換える）のが再帰の本質。

👉 覚え方：「f(n) = n × f(n-1)」、止まる条件は f(0)=1。

ほかの選択肢：a 足し算で違う／b n-1だけ＝nを掛けてない／d 順序がおかしい。

なぜこれが正解か

正解は c（n × f(n-1)）。

階乗の定義 n! = n × (n-1) × (n-2) × ... × 1 を再帰関数で表現すると：

• 基底条件（base case）：f(0) = 1
• 再帰条件（recursive case）：f(n) = n × f(n-1)（n > 0）

例：f(5) = 5 × f(4) = 5 × 4 × f(3) = 5 × 4 × 3 × f(2) = ... = 5 × 4 × 3 × 2 × 1 × f(0) = 5 × 4 × 3 × 2 × 1 × 1 = 120

各選択肢の解説

• a n + f(n-1)：足し算なので階乗にならない（和の再帰）
• b -1 + f(n)：自己参照で無限再帰、停止しない
• c n × f(n-1)：正解。階乗の標準再帰定義
• d (n-1) × f(n)：自己参照(f(n))で無限ループ

覚え方・ひっかけ注意

再帰関数の2要素：

1. 基底条件（再帰を止める条件）：f(0) = 1

2. 再帰条件（自己を縮小して呼び出す）：f(n) = n × f(n-1)

「終わる条件」と「縮小ステップ」の両方が必須。fが再帰呼び出しでnを変えていない（dのf(n)）と無限ループ。試験では基底条件が漏れている／引数が縮小しないパターンが頻出ひっかけ。

理論的背景

再帰（recursion）は計算機科学の基本概念で、自己参照的定義により問題を縮小しながら解く手法。自然数の数学的帰納法と等価な構造を持つ。再帰の実行はコールスタックにフレーム（引数・ローカル変数・戻りアドレス）を積みながら進み、基底条件到達後にスタックを巻き戻す（リターン）。深い再帰はスタックオーバーフローを引き起こすため、末尾再帰最適化（TCO: Tail Call Optimization）で反復化する。

実務での使われ方

再帰的アルゴリズムの典型：

• 分割統治法：マージソート・クイックソート・FFT
• 木の探索：DFS・木構造の操作
• 動的計画法（DP）：メモ化再帰
• バックトラック：N Queen・数独ソルバ
• 再帰下降構文解析：コンパイラのパーサ

パフォーマンス上の注意：

• 単純な階乗・フィボナッチは反復実装の方が高速・低メモリ
• 反復不可能な木構造操作では再帰が自然
• メモ化（memoization）で計算結果キャッシュ → 指数時間を多項式時間に
• 末尾再帰はコンパイラ最適化で反復に変換（Scheme、Erlang、Scalaで保証、JavaScriptは未対応）

試験での位置づけ

プログラミング・アルゴリズム分野の頻出テーマ。基本情報では再帰関数の定義・トレース、応用情報では再帰式の解析（マスター定理）・再帰vs反復の選択・メモ化・末尾再帰まで踏み込む。

選択肢の発展補足

再帰の発展概念：

• 相互再帰：2関数が互いに呼び出し（A→B→A→B...）
• 木再帰：複数の自己呼び出し（フィボナッチ：f(n)=f(n-1)+f(n-2)）
• 線形再帰：1度だけ自己呼び出し（階乗）
• 末尾再帰：再帰呼び出しが関数の最終操作（最適化可能）

ラムダ計算ではYコンビネータで名前なし再帰を実現、関数型プログラミングの基礎。Pythonはsys.setrecursionlimit()でデフォルト1000のスタック深度制限あり、深い木構造処理では明示的スタックでの反復化が安全。動的計画法（DP）は再帰＋メモ化＋ボトムアップ反復の総称で、最適化問題（最短経路・ナップサック・編集距離）の核心技法。試験対策は基本的な再帰定義の理解＋反復との変換＋DPへの拡張で応用情報以上を狙える。