このページでは、自分自身を呼び出す再帰関数の考え方と、階乗・最大公約数の再帰的な定義、再帰を使って2分探索木を探す方法がわかります。
- 一言で言うと：
- 関数の中で自分自身を呼び出す「再帰」の話。階乗や最大公約数のような計算と、木の探索で使う例が出てくる。午前の頻出計算問題があるテーマ。
再帰関数の定義（階乗、最大公約数）→ 木の探索で使う（探索関数）
覚え方の軸
- 再帰関数は「止まる条件」と「1つ小さい自分を呼ぶ式」の2つでできている：
- 階乗なら、n＝0で1を返す（止まる）、それ以外はn×f(n−1)（自分を呼ぶ）
- 再帰は「下りて行って、帰りに計算する」：
- f(3) → f(2) → f(1) → f(0)と呼び出し、f(0)＝1が返ってきてから、1 → 1 → 2 → 6と掛け算していく
- 計算問題は「式に数字を入れて1行ずつ書き下す」だけ：
- F(252, 105)のような問題は、止まる条件（y＝0）になるまで書き換える
- 木は再帰的な構造なので、再帰と相性がよい：
- 左（右）部分木を探すには、左（右）の子へのポインタを引数にして自分を呼ぶ
再帰関数：自分で自分を呼ぶ関数
- 再帰関数：
- 関数の定義の中で、自分自身を使って定義する関数
- 階乗関数（n！）：
- 再帰関数の代表
- n！＝n×（n−1）×（n−2）×…×2×1
- 定義1（プログラムの形）：
- f(n)：if n＝0 then return 1 else return n×f(n−1)
- 受け取ったnが0なら1を返し、それ以外ならn×(n−1)！を返す
- 定義2（数式の形）：
- n＞0のとき f(n)＝n×f(n−1)、n＝0のとき f(n)＝1
- 漸化式：
- 定義2のような式。f(1)、f(2)、…、f(n)、…という関数の列で、f(1)〜f(n)のいくつかを使ってf(n＋1)を求める法則を表す式
- 3！を求める流れ
- ① f(3)：
- nが0でないので、f(2)を呼び出す
- ② f(2)：
- nが0でないので、f(1)を呼び出す
- ③ f(1)：
- nが0でないので、f(0)を呼び出す
- ④ f(0)：
- nが0だから1を返す
- ⑤ f(1)：
- 1×1＝1を返す
- ⑥ f(2)：
- 2×1＝2を返す
- ⑦ f(3)：
- 3×2＝6を返す
- ポイント：
- 呼び出しの途中の状態はスタックに積まれ、後から呼んだものから先に終わる（LIFO）
- ① f(3)：
- 例題：
- f(4)＝4×f(3)＝4×6＝24
- ★頻出パターン（最大公約数を求める再帰関数）
- 定義：
- F(x, y)：y＝0のときx、y＞0のとき F(y, x mod y)
- mod は割り算の余り
- F(252, 105)の値は？
- ＝F(105, 252 mod 105)＝F(105, 42)（252÷105＝2余り42）
- ＝F(42, 105 mod 42)＝F(42, 21)（105÷42＝2余り21）
- ＝F(21, 42 mod 21)＝F(21, 0)（42÷21＝2余り0）
- ＝21（y＝0なのでxを返す）
- これはユークリッドの互除法で、答えは252と105の最大公約数（252＝2²×3²×7、105＝3×5×7なので3×7＝21。検算OK）
- 定義：
- 例題：
- F(48, 18)＝F(18, 12)＝F(12, 6)＝F(6, 0)＝6（48と18の最大公約数は6）
再帰関数の実例：2分探索木を再帰で探す
- 再帰的な構造：
- 自分自身の一部が、自分自身と同じ形をしている構造。木構造がその代表。だから木を使った探索には再帰処理が便利
- ノードのデータ構造：
- value：
- ノードがもつデータ
- left：
- 左の子のノードを指すポインタ
- right：
- 右の子のノードを指すポインタ
- 子がない場合は nil
- value：
- ポインタの書き方：
- 変数pがあるノードへのポインタのとき、そのノードのメンバは p->value、p->left、p->right と書く
- p->leftの値をpに代入すると、pは左の子へのポインタになる
- 探索関数search（データxが2分探索木の中にあるかを判定する）
function search( x, p )
// x：探したいデータ、p：今見ているノードへのポインタ
if ( p が nil )
return FALSE // 行き止まり＝見つからない
endif
if ( x ＝ p->value )
return TRUE // 見つかった
elseif ( x ＜ p->value )
return search( x, p->left ) // 小さいので左部分木で自分を呼ぶ
else
return search( x, p->right ) // 大きいので右部分木で自分を呼ぶ
endif
endfunction
- 流れ：
- pがnil（もう進む先がない）→ FALSE
- xとp->valueが等しい → TRUE
- xの方が小さい → 左部分木を探す、大きい → 右部分木を探す
- ★試験では、再帰呼出しのときの引数が問われる
- 左（右）部分木を探すには、左（右）部分木の根のノードへのポインタ（p->left、p->right）を引数にして、自分自身を呼び出せばよい
混同しやすいペア
- 止まる条件（n＝0なら1、y＝0ならx）／自分を呼ぶ式（n×f(n−1)、F(y, x mod y)）
- 呼び出す順（f(3)→f(2)→f(1)→f(0)）／計算が終わる順（f(0)→f(1)→f(2)→f(3)、スタックなので逆順）
- F(x, y)の引数の入れ替わり：
- 次の呼び出しでは、yが前に、x mod yが後ろに来る
- p->left（左の子へのポインタ、小さいとき）／p->right（右の子へのポインタ、大きいとき）
- FALSE（pがnil＝見つからない）／TRUE（p->valueと等しい＝見つかった）