再帰のトレース｜呼び出しを下へ書き、下から埋める【基本情報技術者試験科目B】

再帰（関数が、その中で自分自身を呼ぶこと）のプログラムは、自分を呼んだ先を追っているうちに「さっきの呼び出しはどうなったのか」を見失いがちです。呼び出しを1行ずつ下へ書き、いちばん下から値を埋めて戻る。この書き出し方を、1 から n までの和を返す5行の関数で確かめます。

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

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

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

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

追いかけるプログラム ── 1 から n までの和を返す wa
wa(3) を1行ずつ動かす ── 呼び出しが積み上がり、戻りながら値が決まる
書き出し方 ── 下へ書いて、下から埋める
次に読む

追いかけるプログラム ── 1 から n までの和を返す wa

関数 wa は、0 以上の整数 n を受け取って、1 から n までの整数の和を返します。n が 0 のときは 0 を返します。

○整数型: wa(整数型: n)
  if (n ＝ 0)
    return 0
  endif
  return n ＋ wa(n － 1)

wa(3) を呼び出すと、6 が返ります。1 から 3 までの和です。

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

ここで1つ困ります。wa(3) の最後の行 3 ＋ wa(2) は、wa(2) の値が返ってくるまで足し算ができません。その wa(2) も、wa(1) が返ってくるまで足し算ができません。この「返ってくるのを待っている呼び出し」を見失わないことが、再帰を追うときのすべてです。

wa(3) を1行ずつ動かす ── 呼び出しが積み上がり、戻りながら値が決まる

下の装置で、wa(3) を1行ずつ進めてください。見るのは「いる場所」の欄です。右端がいま実行している呼び出しで、その左に並んでいるのが、自分を呼んだ行で止まって待っている呼び出しです。

wa(3) を1行ずつ動かす

当サイトオリジナルの例題

ループ開始前

いま計算していること

まだ計算していません

変数の状態

動かして見えたことは、2つです。

呼び出しが積み上がる

自分を呼ぶと、呼んだ側は、自分を呼んだ行で止まって待ちます。終わったわけではありません。wa(0) が呼ばれた時点で、wa(3)・wa(2)・wa(1) の3つが待っていました。n も呼び出しごとに1つずつあり、wa(0) から wa(1) に戻ったとき、n は 0 ではなく 1 に戻っていました。

戻りながら値が決まる

値が最初に決まるのは、最後に呼ばれた wa(0) です。そこから wa(1) が 1、wa(2) が 3、wa(3) が 6 と、呼んだのと逆の順に決まりました。wa(0) で止まれるのは、n ＝ 0 のとき自分を呼ばずに return 0 で返すからです。

書き出し方 ── 下へ書いて、下から埋める

A8-1 の置き換えと同じことを、呼び出しが増えても崩れない表の形で書きます。試験の画面に、この装置はありません。上の装置がやったことを、自分の手で書き出します。1行に呼び出しを1つ書き、列は「呼び出し」「n」「返す式」「返す値」の4つにします。

再帰の書き出し方

```
  return n ＋ wa(n － 1)
```
最初の呼び出しを1行目に書く。自分を呼ぶ行に来たら、下に1行足す。いまの行の「返す式」には n に値を入れた式（3 ＋ wa(2)）を書き、「返す値」は空けておきます。新しい行は、呼ばれた wa(2) のぶんです。どの行がどの行に呼ばれたかが見えるよう、1段字下げして書きます。
```
  if (n ＝ 0)
    return 0
  endif
```
自分を呼ばずに返す行に着いたら、その呼び出しの「返す式」と「返す値」を書く。wa(0) なら、どちらも 0 です。下へ書き足すのは、ここで終わりです。
下の行から上へ、「返す値」を1行ずつ埋める。1つ下の行の返す値を、止まっていた式の wa のところに入れて、足し算の続きをします。

wa(3) を、この手順で書き出すとこうなります。

wa(3) の書き出し ── 下へ書いて、下から埋める

1行＝呼び出し1つ　／　字下げが深い行ほど、あとから呼ばれた呼び出し　／　？＝まだ書けない　／　色の付いたマス＝そこで決まった値

前：手順1・2 ── 自分を呼ばずに返す行に着くまで、下へ書いたところ

呼び出し	n	返す式	返す値
wa(3)	3	3 ＋ wa(2)	？
wa(2)	2	2 ＋ wa(1)	？
wa(1)	1	1 ＋ wa(0)	？
wa(0)	0	0	0

上の3行は、返す式に wa が残っているので、返す値をまだ書けません。

後：手順3 ── 下の行から上へ、返す値を埋めたところ

呼び出し	n	返す式	返す値
wa(3)	3	3 ＋ 3	6
wa(2)	2	2 ＋ 1	3
wa(1)	1	1 ＋ 0	1
wa(0)	0	0	0

1つ下の行の返す値を、返す式の wa のところに入れて足します。埋まる順は、下から 1 → 3 → 6 です。

いちばん上の行の返す値 6 が、wa(3) の答え

下へ書くのが「呼び出しが積み上がる」、下から埋めるのが「戻りながら値が決まる」です。行を1つも消さずに残しておくので、どの呼び出しが待っているか、そのときの n がいくつかを、頭に置いておかなくて済みます。

本物もこう書かれる

（令和8年度基本情報技術者試験科目B 公開問題問3）

  return 2 × func1(n － 2) ＋ func1(n － 1)

関数 func1 の最後の行です。1行の中で自分を2回呼んでいます。この形でも、呼んだ側がこの行で止まって待つことと、自分を呼ばずに返す行に着いたところから値が決まることは変わりません。呼び出しが2つあるぶん、書き出しの行は途中で枝分かれします。この問題での値の出し方は令和8年度問3の解説にあります。

次に読む

A9	スタックとキュー ─ あとから入れたものを先に出す
A8-1	再帰とは ─ 自分を呼ぶ関数と、終了条件
問7	サンプル問題問7の解説 ─ 階乗を返す関数 factorial
目次	基本情報技術者試験科目B 攻略ガイド