再帰関数とは？終了条件と効率的な展開方法【基本情報技術者試験】

まず結論

再帰関数は、関数の中で自分自身を呼び出す関数です。

試験では、次の3点を確認します。

自分自身を呼び出す
→ 再帰関数

再帰を止める条件
→ 終了条件

引数が終了条件へ近づく
→ 正常に終了できる

さらに、値を求める問題では、何を求めたいかによって計算の向きを選ぶと効率的です。

特定の1個の値を求めたい
→ 求める値から必要な部分だけ展開する

表全体や多くの値を求めたい
→ 終了条件に近い値から順に計算する

まずは、求める値から式を展開し、終了条件に到達したら下から戻る方法を基本にすると迷いにくくなります。

直感的な説明

再帰は、階段を一段ずつ下りるイメージです。

5段目
↓
4段目
↓
3段目
↓
2段目
↓
1段目で停止

一番下まで進んだら、結果を逆向きに戻しながら計算します。

例えば、次の関数を考えます。

f(n):
  n ≦ 1 なら1を返す
  それ以外なら n + f(n - 1) を返す

f(5)は次のように展開できます。

f(5)
= 5 + f(4)
= 5 + 4 + f(3)
= 5 + 4 + 3 + f(2)
= 5 + 4 + 3 + 2 + f(1)
= 5 + 4 + 3 + 2 + 1
= 15

ここで大切なのは、最初から f(1), f(2), f(3) と全部を順番に作る必要はないことです。

欲しい値は f(5)
↓
f(5) を求めるために必要な f(4) を見る
↓
f(4) を求めるために必要な f(3) を見る
↓
終了条件まで進む

今ほしい値から必要な値だけをたどると、計算する範囲を絞れます。

定義・仕組み

再帰関数に必要な二つの部分

再帰関数には、基本的に次の二つが必要です。

終了条件

n ≦ 1 なら1を返す

これ以上、自分自身を呼び出さない条件です。

再帰処理

n + f(n - 1)

問題を少し小さくして、自分自身をもう一度呼び出します。

終了条件
→ 再帰を止める

再帰処理
→ 問題を小さくして続ける

呼出しと戻り値の流れ

再帰関数では、まず呼出しが深く進みます。

f(5)
→ f(4)
→ f(3)
→ f(2)
→ f(1)

f(1)で終了条件に到達すると、結果が逆向きに戻ります。

f(1) = 1
f(2) = 2 + 1 = 3
f(3) = 3 + 3 = 6
f(4) = 4 + 6 = 10
f(5) = 5 + 10 = 15

1回の呼出しから二つに枝分かれする再帰

再帰式は、必ず1本の鎖になるとは限りません。

例えば、次のような関数を考えます。

g(n, k) = 1                    （k = 0 または k = n）
g(n, k) = g(n-1, k-1) + g(n-1, k)  （それ以外）

g(4,2)だけを求めたいなら、まず目的の値から展開します。

g(4,2)
= g(3,1) + g(3,2)

さらに必要な値だけ追います。

g(3,1)
= g(2,0) + g(2,1)

g(3,2)
= g(2,1) + g(2,2)

g(2,0)とg(2,2)は終了条件なので、その場で 1 と分かります。

残る g(2,1)だけを計算します。

g(2,1)
= g(1,0) + g(1,1)
= 1 + 1
= 2

したがって、

g(3,1) = 1 + 2 = 3
g(3,2) = 2 + 1 = 3

g(4,2) = 3 + 3 = 6

このように、枝分かれする再帰でも、求める値から必要な枝だけを展開するのが基本です。

同じ値が何度も出てきたら再利用する

上の例では、g(2,1)が2回現れました。

g(3,1) の中に g(2,1)
g(3,2) の中にも g(2,1)

一度 g(2,1) = 2 と求めたら、もう一度最初から展開する必要はありません。

同じ式が出てきた
→ すでに求めた値を再利用する

試験で手計算するときも、この意識だけで計算量を減らせます。

スタックとの関係

関数を呼び出すたびに、処理途中の情報がスタックへ積まれます。

呼出し
→ 後から呼んだ関数が上に積まれる

戻り
→ 後から呼んだ関数から先に戻る

これは、スタックの後入れ先出し（LIFO）という性質です。

スタックそのものの仕組みは、スタックとキューの違いとあわせて確認するとつながりやすくなります。

科目Aでどう出る？

科目Aでは、次の内容が問われます。

再帰関数の定義
終了条件
引数の変化
戻り値の計算
無限再帰になる条件
再帰式を展開して特定の値を求める問題

基本の解く順番は次のとおりです。

終了条件を探す
求めたい値を確認する
その値から必要な部分だけ展開する
終了条件に到達したら止める
下から戻り値を計算する

どちら向きに計算するかを決める

再帰式を見ると、終了条件側から順番に値を作りたくなることがあります。

その方法でも解けますが、問題によっては余分な値まで計算することになります。

判断の目安は次です。

求めたいもの	おすすめの考え方
特定の1個の値	求める値から逆向きに必要な式だけ展開
同じ段の多くの値	終了条件側から表のように順番に計算
再帰の呼出し順	求める値から呼出しを追う
戻り値	終了条件に着いた後、下から戻る

一言でまとめると、

1個だけ欲しい
→ 上から必要な枝を掘る

たくさん欲しい
→ 下から表を作る

です。

合計と階乗の切り分け

演算子を必ず確認します。

n + f(n - 1)
→ 1からnまでの合計

n × f(n - 1)
→ 階乗

例えば、

5 + 4 + 3 + 2 + 1
→ 15

5 × 4 × 3 × 2 × 1
→ 120

となります。

階乗に特化した再帰式は、再帰関数とは？階乗の再帰式と終了条件の見抜き方でも整理しています。

科目Bでどう使う？

科目Bでは、再帰関数の擬似言語を追跡するときに使います。

確認するポイントは次のとおりです。

どの条件で再帰が止まるか
引数が呼出しごとにどう変わるか
1回の呼出しから何個の再帰呼出しが発生するか
呼出しが何段まで深くなるか
戻り値がどの順番で計算されるか

1本の再帰なら表にすると追跡しやすくなります。

呼出し	引数	次の処理
`f(5)`	5	`5 + f(4)`
`f(4)`	4	`4 + f(3)`
`f(3)`	3	`3 + f(2)`
`f(2)`	2	`2 + f(1)`
`f(1)`	1	`1を返す`

枝分かれする再帰なら、簡単な木として書くと見失いにくくなります。

        g(4,2)
       /      \
   g(3,1)    g(3,2)
    /  \      /  \
   1  g(2,1) g(2,1) 1
       / \     / \
      1   1   1   1

ただし、同じ g(2,1) が出てきたら、一度求めた結果を再利用します。

よくある誤解・混同

終了条件側から全部求めないといけない

終了条件から順番に計算しても正解できます。

ただし、特定の値だけを求める問題では、不要な値まで計算することがあります。

求める値を確認
↓
必要な値だけ展開

という順番を意識すると効率的です。

`f(1)`でも再帰呼出しを続ける

終了条件がn ≦ 1なら、f(1)はその場で終了します。

f(1) = 1

であり、1 + f(0)ではありません。

終了条件を確認しない

再帰関数では、最初に終了条件を探します。

終了条件
引数の変化
終了条件へ近づくか

この3点を確認します。

同じ値を何度も展開する

枝分かれする再帰では、同じ部分問題が繰り返し現れることがあります。

一度値を求めたらメモして使い回すと、手計算を減らせます。

合計と階乗を混同する

+と×を読み違えないことが重要です。

再帰関数は必ず無限に続く

終了条件があり、引数がその条件へ近づけば終了します。

f(n - 1)
→ nが小さくなる
→ 終了条件へ近づく

一方、引数が変わらなかったり、終了条件から遠ざかったりすると無限再帰になります。

まとめ（試験直前用）

自分自身を呼び出す関数が再帰関数
最初に終了条件と引数の変化を確認する
1個の値を求めるなら、求める値から必要な部分だけ展開する
終了条件に到達したら、下から戻り値を計算する
同じ部分問題が出てきたら、求めた値を再利用する
表全体を求めるなら、終了条件側から順に計算する方法も有効

一言で覚えるなら、

1個なら上から必要な枝を掘り、終了条件に着いたら下から戻る。

🔗 関連記事

🏠 基本情報技術者トップに戻る