再帰とは｜自分を呼ぶ関数と、終了条件【基本情報技術者試験科目B】

再帰とは、関数が、その中で自分自身を呼び出すことです。はじめて見ると「まだ読み終えていない関数を、その中で使ってよいのか」と手が止まりますが、読み方はほかの関数の呼び出しと変わりません。階乗を返す5行の関数で確かめます。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円~~2,600円~~中身を見る ›

この回の内容を動画で見る

講義の実際の画面公開記念・いまだけ先着100名0円~~通常 2,600円~~有料講座「科目B 基礎講義」プログラムを1行ずつたどり、値がどう変わるかを動画で見せます。この回の講義もこの講座に入っています。講義の目次と無料の1本を見るUdemy・12月3日まで・100名に達したら通常価格に戻ります

次のページで講義の目次と無料の講義を見られます。受講ボタンとクーポンコードもそこにあります。

再帰とは ── 関数が、自分自身を呼ぶ
階乗で確かめる ── kaijou(3) が 6 を返すまで
終了条件 ── 自分を呼ばずに返す行
次に読む

再帰とは ── 関数が、自分自身を呼ぶ

n の階乗は、1 から n までの整数を全部掛けた数です。3 の階乗なら 3 × 2 × 1 ＝ 6。次の関数 kaijou は、1 以上の整数 n を受け取って、その階乗を返します。

○整数型: kaijou(整数型: n)
  if (n ＝ 1)
    return 1
  endif
  return n × kaijou(n － 1)

kaijou(3) を呼び出すと、6 が返ります。

最後の行を見てください。kaijou の中で、kaijou を呼んでいます。これが再帰です。

自分を呼ぶ式になるのには理由があります。3 の階乗 3 × 2 × 1 のうち、うしろの 2 × 1 は 2 の階乗です。つまり 3 の階乗＝ 3 ×（2 の階乗）。n で書くと「n の階乗＝ n ×（(n － 1) の階乗）」で、最後の行 return n × kaijou(n － 1) は、これをそのまま書いたものです。

自分を呼ぶ式の読み方

ほかの関数の呼び出しと同じです。その関数を最初の行から実行し、返ってきた値を、呼び出しが書いてあった場所に入れます。

関数の呼び出しと return の読み方は G3-3 戻り値にあります。

階乗で確かめる ── kaijou(3) が 6 を返すまで

kaijou(3) が返す値を、自分の手で出します。式の中に kaijou(2) のような kaijou の呼び出しが出てきたら、その呼び出しが return する式を、かっこに入れて同じ場所に書きます。返ってくる値がまだ分からないので、値の代わりに式のまま置いておく、ということです。これを、呼び出しが無くなるまで続けます。

kaijou(3) が返す値 ── 呼び出しを、返す式で置き換えていく

太字＝その段で置き換えたところ

① kaijou(3) を呼ぶ（n は 3）

kaijou(3) ＝ 3 × kaijou(2)

3 は 1 ではないので if の中には入らず、最後の行 return n × kaijou(n － 1) へ進みます。n に 3 を入れると 3 × kaijou(2)。kaijou(2) がいくつかは、まだ分かりません。

② kaijou(2) を置き換える（n は 2）

kaijou(3) ＝ 3 × (2 × kaijou(1))

kaijou(2) も、関数の最初の行から実行します。2 は 1 ではないので、返すのは 2 × kaijou(1)。これをかっこに入れて、kaijou(2) があった場所に書きます。n は呼び出しごとに別で、kaijou(2) の中の n が 2 でも、kaijou(3) の n は 3 のままです。

③ kaijou(1) を置き換える（n は 1）

kaijou(3) ＝ 3 × (2 × 1)

n が 1 なので、今度は if の中の return 1 です。自分を呼ばずに 1 を返すので、＝の右側から kaijou が消えました。

④ 掛け算する

kaijou(3) ＝ 6

かっこの中から計算します。2 × 1 ＝ 2（これが kaijou(2) の返す値です）、3 × 2 ＝ 6。kaijou(3) が返す値は 6 です。

＝の右側に kaijou が残っているあいだは置き換える。消えたら計算する

終了条件 ── 自分を呼ばずに返す行

置き換えが終わったのは、kaijou(1) が自分を呼ばずに 1 を返したからです。自分を呼ばずに返す行へ入る条件（kaijou では n ＝ 1）を、再帰の終了条件といいます。

再帰が終わるのは、自分を呼ばずに返す行があり、しかも、自分を呼ぶたびに引数が変わって、いつか終了条件に当てはまるときです。

どちらかが欠けるとどうなるかを、kaijou(3) で見ておきます。

どちらかが欠けると、置き換えが終わらない

どちらも kaijou(3) を呼び出したとき

自分を呼ばずに返す行が無い ── if の3行を消したとき

○整数型: kaijou(整数型: n)
  return n × kaijou(n － 1)

kaijou(3) ＝ 3 × kaijou(2)
　＝ 3 × (2 × kaijou(1))
　＝ 3 × (2 × (1 × kaijou(0)))　…

kaijou(1) も自分を呼びます。引数は 1 を通り過ぎて 0、－1、－2 と小さくなり続け、何回置き換えても＝の右側に kaijou が残ります。呼び出しが残っているあいだは掛け算を始められないので、返す値がいつまでも決まりません。

引数が変わらない ── n － 1 を n と書いたとき

○整数型: kaijou(整数型: n)
  if (n ＝ 1)
    return 1
  endif
  return n × kaijou(n)

kaijou(3) ＝ 3 × kaijou(3)
　＝ 3 × (3 × kaijou(3))
　＝ 3 × (3 × (3 × kaijou(3)))　…

自分を呼ばずに返す行はあっても、n が 3 のまま変わりません。n ＝ 1 が成り立つときが来ないので、こちらも返す値が決まりません。

だから、再帰のプログラムを読むときは、値を追う前にこの2つを探します。先に見つけておけば、置き換えがどこで終わるかが分かったうえで始められます。

再帰を見たら、先に探す2つ

```
  if (n ＝ 1)
    return 1
  endif
```
自分を呼ばずに返す行。引数がいくつのときに、何を返すかを読みます。kaijou は「n が 1 のとき 1」。
```
  return n × kaijou(n － 1)
```
自分を呼ぶ行で渡している引数。呼ぶたびにどう変わるかを読みます。kaijou は 1 ずつ減るので、1 以上の整数から始めれば必ず 1 に着きます。

本物もこう書かれる

（基本情報技術者試験科目B サンプル問題問7）

  if (n ＝ 0)
    return 1
  endif

階乗を返す関数 factorial の、終了条件の3行です。この出題は問題文で「非負の整数n の階乗はn が0 のときに1 になり」と決めているので、終了条件は n ＝ 0 になっています。自分を呼ぶ行のほうが空欄で、入る式を解答群から選びます（サンプル問題問7の解説）。

次に読む

A8-2	再帰のトレース ─ 呼び出しを下へ書き、下から埋める
問7	サンプル問題問7の解説 ─ 階乗を返す関数 factorial
G3-3	戻り値 ─ return で値が返るまで
目次	基本情報技術者試験科目B 攻略ガイド