再帰呼び出しのアルゴリズム|新しい擬似言語で学ぶ 科目 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 関数を呼び出していることに注目してください。 これが再帰呼び出しです。

swipeプログラムは横スクロールできます

リスト 1code 引数 n の階乗を返す 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 には、もう 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 が求められます。

再帰呼び出しの穴埋め問題にチャレンジする

試験対策として、プログラムの穴埋め問題にチャレンジしてみましょう。

これまでに例として示したプログラムと同じ内容ですが、再帰呼び出しの定番の例なので、確実に覚えてください。

リスト 2 は、引数 n の階乗を返す factorial 関数の定義です。 プログラム中の に入る正しい答えの組合せを解答群の中から選んでください。 引数 n は、 0 以上だとします。

リスト 2code 引数 n の階乗を返す factorial 関数の定義
整数型: 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 関連タグ
科目A試験は、
免除できます。
独習ゼミで科目A試験を1年間免除して、科目B試験だけに集中しましょう。
免除試験を受けた 74.9% の方が、
科目A免除資格を得ています。
科目A免除試験 最大 2 回の
受験チャンス !
info_outline
科目A免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門』の連載一覧

マージソート|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

二分木の深さ優先探索と幅優先探索|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

比べてわかるキューとスタックの仕組み|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

「リスト」というデータ構造|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

サーチのアルゴリズム (3) ハッシュ表探索法のアルゴリズム|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

クイックソートのアルゴリズム|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

再帰呼び出しのアルゴリズム|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

サーチのアルゴリズム (2) 二分探索法|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

サーチのアルゴリズム (1) 線形探索法|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update

多重ループを使うバブルソート|新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update
label 著者