再帰呼び出しのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
2023-06-06 更新
基本情報技術者試験は、 2023 年 4 月から新制度で実施されています。
この連載では、新制度で採用された新しい擬似言語（旧制度の擬似言語とは、表記方法に違いがあります）を使って、試験のシラバス（情報処理技術者試験における知識・技能の細目）に示されている代表的なアルゴリズムとデータ構造を、プログラミング入門者向けにやさしく解説します。 受験対策としてだけでなく、アルゴリズムとプログラミングの基礎知識を習得するために、ぜひお読みください。
今回は 再帰呼び出し を取り上げます。
再帰呼び出しとは？
再帰呼び出し（ recursive call ）とは、「関数の処理の中で同じ関数を呼び出すことで繰り返しを実現する」というプログラミング・テクニックです。
プログラムで繰り返しを実現するには、 while 文や for 文を使う方法がありますが、それらとは別に再帰呼び出しという方法もあるのです。
再帰呼び出しの仕組みを説明するための代表的な例として、「引数で指定した数の階乗を返す関数」があります。 階乗とは、その数から 1 までのすべての数を掛けた値です。
たとえば、 5 の階乗は、
5 × 4 × 3 × 2 × 1 = 120
です。 数学の約束で、 0 の階乗は 1 と決められています。
リスト 1 は、引数 n （ 0 以上だとします）の階乗を返す factorial 関数の定義です。 factorial は、「階乗」という意味です。 factorial 関数の処理の中で同じ factorial 関数を呼び出していることに注目してください。 これが再帰呼び出しです。
○整数型: factorial(整数型: n) if (n = 0) return 1 else return n × factorial(n - 1) // これが再帰呼び出し endif
リスト 1 では、
「 n の階乗は、 n × (n – 1) の階乗である」
という考えで、階乗を求めています。 たとえば、 5 の階乗は、
5 × 4 × 3 × 2 × 1
ですが、これは
5 × ( 4 の階乗)
と考えることができます。
階乗を求める処理の中で、階乗を求める処理を使うことが、再帰呼び出しになるのです。
n × factorial(n - 1)
の部分は、
「 n の階乗は、n × (n – 1) の階乗である」
という考えをプログラムで表しています。
再帰呼び出しの仕組み
それでは、どうして再帰呼び出しで繰り返しが実現されるのでしょうか？ それは、関数を呼び出すと、関数の入り口から処理が行われるからです。
図 1 に示したように、 factorial 関数の処理の中で同じ factorial 関数を呼び出すと、 factorial 関数の処理が繰り返されます。
リスト 1 には、もう 1 つ注目してほしい部分があります。 それは、再帰呼び出しによる繰り返しが終わる部分です。
if (n = 0) return 1
関数の処理の中で同じ関数を呼び出すというだけでは、永遠に処理が繰り返される無限ループになってしまいます。 そこで、 factorial 関数では、 if 文を使って、もしも引数 n が 0 なら再帰呼び出しを行わずに return 1 で戻り値として 1 を返しています（数学の約束で、 0 の階乗は 1 と決められているからです）。 これによって、再帰呼び出しによる繰り返しが終わるのです。
このように、再帰呼び出しを使うプログラムは、多くの場合に、 if 文を使って、ある条件なら同じ関数を呼び出して繰り返しを行い、ある条件なら同じ関数を呼び出さずに繰り返しを終える、という内容になります。
再帰呼び出しの処理の流れ
ここまでの説明で、再帰呼び出しの仕組みが何となくわかったと思いますが、 factorial 関数で引数 n の階乗が得られるまでの処理の流れがピンと来ないでしょう。
具体例として、引数 n = 3 のときの処理の流れをトレースしてみましょう。 3 の階乗は、
3 × 2 × 1 =6
です。
以下に、 factorial(3) を呼び出したときの処理の流れを示します。
- 手順 counter_1
factorial(3)が呼び出される。- 手順 counter_2
return 3 × factorial(2)が行われ、factorial(2)が呼び出される。- 手順 counter_3
return 2 × factorial(1)が行われ、factorial(1)が呼び出される。- 手順 counter_4
return 1 × factorial(0)が行われ、factorial(0)が呼び出される。- 手順 counter_5
- 1 が返される。
- 手順 counter_6
return 1 × factorial(0)がreturn 1 × 1となって 1 が返される。- 手順 counter_7
return 2 × factorial(1)がreturn 2 × 1となって 2 が返される。- 手順 counter_8
return 3 × factorial(2)がreturn 3 × 2となって 6 が返される。
上記の処理の流れのポイントは、
return n × factorial(n - 1)
において、すぐには戻り値を返す処理が行われずに（処理は保留になります）、 factorial(n - 1) という再帰呼び出しが行われることです。 この再帰呼び出しによる繰り返しは、引数が 0 になったときに return 1 で 1 という戻り値を返すことで終わり、その後は、保留になっていた戻り値を返す処理が繰り返されます。
つまり、
関数を呼んで → 呼んで → 呼んで、と繰り返し、
戻り値を返して → 返して → 返して、と繰り返すのです。
3 の階乗は、 3 × 2 × 1 = 6 ですが、 1 の階乗を求めるときの 1 × (0 の階乗 ) において
1 × 1
という計算が行われるので、 3 × 2 × 1 × 1 = 6 で 6 が求められます。
再帰呼び出しの穴埋め問題にチャレンジする
試験対策として、プログラムの穴埋め問題にチャレンジしてみましょう。
これまでに例として示したプログラムと同じ内容ですが、再帰呼び出しの定番の例なので、確実に覚えてください。
○整数型: factorial(整数型: n) if (n = 0) return a else return b endif
解答群
| a | b | |
|---|---|---|
| ア | 0 | factorial(n – 1) |
| イ | 0 | n × factorial(n – 1) |
| ウ | 1 | factorial(n – 1) |
| エ | 1 | n × factorial(n – 1) |
空欄 a は、引数 n が 0 のときの処理です。 0 の階乗は 1 なので、 return 1 という処理を行い、再帰呼び出しを行いません（再帰呼び出しによる繰り返しが終了します）。
空欄 b は、引数 n が 0 でないときの処理です。 ここでは、「 n の階乗は、 n × (n – 1) の階乗である」という考えで、 n × factorial(n - 1) という処理を行います。
したがって、正解は、選択肢エです。
今回は、再帰呼び出しを取り上げました。
次回以降も、シラバスに示されたアルゴリズムとデータ構造を学んでいきます。
それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
※独習ゼミは、受験ナビ運営のSEプラスによる試験対策eラーニングです。
マージソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
二分木の深さ優先探索と幅優先探索｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
比べてわかるキューとスタックの仕組み｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
「リスト」というデータ構造｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (3) ハッシュ表探索法のアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
クイックソートのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
再帰呼び出しのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (2) 二分探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (1) 線形探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
多重ループを使うバブルソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
