再帰（recursion）

分類

テクノロジ系 アルゴリズムとプログラミング

出る試験

基本情報応用情報

重要度

★★★★☆

もう少し詳しい説明

再帰とは、処理の中から、その処理自身を呼び出す書き方です。「自分を呼ぶ」と聞くと堂々めぐりに思えますが、呼ぶたびに問題が小さくなっていくので、いつか終わります。

使えるのは、元の問題が、同じ形の小さい問題で言い表せるときです。

階乗で見る

階乗は、その数から1まで、順に掛けていったものです。

3 の階乗 ＝ 3 × 2 × 1 ＝ 6
5 の階乗 ＝ 5 × 4 × 3 × 2 × 1 ＝ 120

ふつうに読めばこれで終わりです。ここからが再帰の話になります。

中に、一回り小さい同じものが入っている

3の階乗と、2の階乗を並べて書いてみます。

3 の階乗 ＝ 3 × 2 × 1
2 の階乗 ＝ 2 × 1

下の行がまるごと、上の行のうしろの部分になっています。 つまり 3の階乗 ＝ 3 ×（2の階乗） と書けます。

同じことが、どの数でも成り立ちます。

n の階乗 ＝ n ×（n−1 の階乗）

一回り小さい同じ問題が、中に入っている。 これが「再帰で書ける形」です。

プログラムにすると

上の式をそのまま書き写すと、こうなります。階乗を求める処理に fact という名前を付けました。

fact(n):
    n が 1 なら、1 を返す
    そうでなければ、n × fact(n−1) を返す

3行目で、fact が fact を呼んでいます。 これが再帰です。

2行目も同じくらい大事です。 これが無いと、1の次は0、その次は−1と、いつまでも小さくなり続けて終わりません。どこで止まるかを決めているのが2行目です。

動かしてみる

fact(3) を呼ぶと、どうなるか。

fact(3) は、いきなり答えを出せません。3 × fact(2) の fact(2) が分からないと掛け算ができないので、計算を途中で止めたまま fact(2) を呼びます。fact(2) も同じ理由で fact(1) を呼びます。

起きることを、1つずつ追います。矢印のうしろは、その時点で求めたい式です。

1. fact(3) … 3 は 1 ではないので fact(2) を呼ぶ → 3 × fact(2)
2. fact(2) … 2 は 1 ではないので fact(1) を呼ぶ → 3 ×（2 × fact(1)）
3. fact(1) … 1 なので、1 を返す → 3 ×（2 × 1）
4. fact(2) に 1 が戻る … 2 × 1 を計算して 2 を返す → 3 × 2
5. fact(3) に 2 が戻る … 3 × 2 を計算して 6 を返す → 6

各行のうしろの式を、上から順に見てください。1と2では式が深くなるだけで、掛け算は1つも行われていません。 掛け算が始まるのは、3で fact(1) が答えを返してからです。

もう1つ、見落としやすい点があります。掛け算は、最後に呼ばれたものから順に片付きます。

2 × 1 を先に計算  →  その答え 2 を使って  →  3 × 2 を計算

書いた順（3 × 2 × 1）とは逆向きです。3 × 2 を先に計算しているわけではありません。

行き止まりまで降りてから、折り返して戻る。 再帰の動きは、いつもこの形です。

• 降りるとき … 掛け算はまだできない。呼び出しだけが積み上がる
• 戻るとき … 下から答えが届き、掛け算が1段ずつ片付く

この積み上がる場所がスタックです。スタックは後に入れたものから先に取り出す構造で、いま見た「最後に呼ばれたものから先に片付く」という順番と、ぴったり一致します。再帰を使うと、自分でスタックを用意しなくても、呼び出しの仕組みがスタックの役目をしてくれます。

止める条件がないと終わらない

さきほどの2行目を、もう少し詳しく見ます。再帰にはこれ以上小さくできないときの答えが必ず要ります。階乗では「n が 1 なら、1 を返す」がそれでした。

これを書き忘れると、呼び出しが延々と積み上がります。積む場所には限りがあるので、やがてあふれて異常終了します。スタックオーバーフローと呼ばれる止まり方です。

止める条件を書いても、そこへ必ず近づいていくようになっていなければ同じです。fact(n) が fact(n) を呼んでいたら、いつまでも1にたどり着きません。

• 止める条件があること
• 呼ぶたびに、その条件へ近づくこと

この2つがそろって、はじめて終わります。

繰返しとの違い

同じことは繰返し（ループ）でも書けます。階乗なら、1から n まで順に掛けていけば済みます。

では何が違うのか。途中の状態を、どこに置くかです。

繰返しでは、途中の値を自分で変数に持ちます。再帰では、呼び出しが積み上がること自体が記録になっていて、変数を用意しなくても元の場所へ戻れます。

そのため、枝分かれして戻ってくる処理では再帰が圧倒的に書きやすくなります。木構造（1つの根から枝が分かれていくデータの持ち方）をたどる処理が代表例で、左の枝を全部見てから右の枝へ移るとき、「どこまで見たか」を自分で覚えておく必要がありません。

逆に、ただ順番に進むだけの処理は繰返しのほうが向きます。呼び出しには場所も時間も要るので、積み上げる必要がないなら積まないほうが速く済みます。

何に使われているのか

木構造をたどる処理がいちばん身近です。フォルダの中のフォルダをすべて見ていく処理は、「このフォルダの中身を見る」という同じ処理をフォルダの数だけ呼ぶ形になります。

整列（ソート）のクイックソートやマージソートも再帰です。「半分に分けて、それぞれを並べ替えて、くっつける」という手順が、そのまま小さい同じ問題になっています。

ハノイの塔やフィボナッチ数列も、試験ではおなじみの題材です。どれも元の問題が、一回り小さい同じ問題で書けるという点が共通しています。

試験ではこう出る

科目A（旧・午前）で出ます。いちばん多いのは、再帰的に定義された関数に具体的な数を入れて、答えを出させる問題です。

解き方は決まっています。定義どおりに、紙の上で展開するだけです。頭の中でやると戻る場所を見失うので、書いて降りて、書いて戻ります。

次に多いのが、再帰の性質を選ばせる問題です。「打ち切りの条件が必要」「スタックを使う」のどちらかが答えになります。再使用可能・再入可能・再配置可能と並べて出されることもあり、そのときは言葉の取り違えが問われています。

科目B（旧・午後）では、再帰を使った擬似言語の処理を追わせる問題が出ます。呼び出しのたびに引数の値が変わるので、呼び出しごとに1行ずつ書き出して追うのが確実です。

関連する用語

スタック

後入先出の構造。再帰の呼び出しは、この形で積み上がって戻る

木構造

枝が分かれていくデータ構造。たどる処理は、ほとんど再帰で書かれる

計算量

件数が増えたときの伸び方。再帰の書き方しだいで、同じ答えでも伸び方が変わる

プログラムの性質

再使用可能・再入可能・再帰的・再配置可能の4つ。「再帰的」はこの再帰が書けるという意味

整列（ソート）

並べ替え。クイックソートやマージソートは、再帰で書くのが自然な形になっている

ミニクイズ

この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）

最終更新：2026-10-09