呼び出しの連鎖

呼ばれた関数が、さらに別の関数を呼ぶ

前回は、main から関数を 1 つ呼ぶ形を追いました。今回は、呼ばれた関数の中からさらに別の関数を呼ぶ形を読みます。本試験の科目 B では、この 2 段の呼び出しがふつうに出てきます。そして次のレッスンからの再帰は、この 2 段が同じ関数どうしで起きているだけです。今回の追いかたが、そのまま再帰の追いかたになります。

深さの列を用意する

呼び出しが重なると、いま自分がどの関数の中にいるのかを見失います。そこで、変数表に「深さ」という列を足します。深さはプログラムの中の変数ではなく、追う人が付ける目印です。main の中にいるときを 0 とし、関数へ入るたびに 1 増やし、return で出るたびに 1 減らします。

深さの列があると、戻ってきた先がどこなのかを迷わずに決められます。深さが 2 から 1 に減ったなら、行き先は 1 段目の関数の、呼び出しを書いた行です。

式の中に呼び出しが 2 つあるとき

return nijou(a) + nijou(b)

この 1 行では、呼び出しが 2 回起きます。順番は左からです。まず nijou(a) を呼んで値を持ち帰り、次に nijou(b) を呼んで値を持ち帰り、そのあとで足し算をして返します。同時に動くことはありません。

ここで大事なのは、左側から持ち帰った値をどこに置くかです。プログラムの中には、その値を入れる変数がありません。ですから追う人が余白に控えます。今回なら 4 という数字を余白に書いておき、右側の 9 が返ってきたところで 4 + 9 とします。この余白の値こそが、実際の計算機が呼び出しスタックに積んでいるものです。

引数が生まれ直すことを確かめる

nijou は 2 回呼ばれます。1 回目は n が 2、2 回目は n が 3 です。1 回目が終わった時点で n はいったん消え、2 回目でまた生まれます。表では、いったん全角ダッシュに戻してから新しい値を書きます。

この「消えて生まれ直す」動きが見えていれば、同じ関数が何段も重なる再帰でも、それぞれの段が別々の n を持っていることが自然に受け入れられます。

追いかたの手順

  1. 呼び出しの行に来たら、深さを 1 増やし、引数の欄を埋める
  2. 呼ばれた関数を最後まで追い、返る値を余白に控える
  3. 深さを 1 減らし、呼び出しを書いた行に戻る
  4. 控えた値を式にはめ、その関数の変数を消す

この手順のうち、いちばん飛ばされやすいのが 3 です。呼ばれた関数の return を見た瞬間に、そのまま main へ戻ってしまう答案がよくあります。戻る先は必ず、自分を呼んだ行です。深さの列を毎回書いておけば、1 段だけ戻るという当たり前のことを取り違えずに済みます。

なお、深さが 3 や 4 まで積み上がっても、追いかたは変わりません。増えるのは表の行数だけです。手順が体になじんでいれば、段数が増えても迷いません。

では下のコードを追ってください。行番号は 1 行目の nijou の定義から数え、空行も 1 行として数えます。

課題

  1. 各行を実行したあとの値を入れる
  2. 値が変わらない変数はそのままの値を入れる
  3. 関数が終わって消えた変数は — を入れる
  4. 深さは関数へ入るたびに 1 増やし、戻るたびに 1 減らす

ヒント

1 / 9 行目のトレース

1○整数型: nijou(整数型: n)
2 return n × n
3 
4○整数型: wa(整数型: a, 整数型: b)
5 return nijou(a) + nijou(b)
6 
7○整数型: main()
8 整数型: kekka
9 kekka ← wa(2, 3)
10 return kekka
実行した行深さnabkekka
実行前0————
9 行目

9 行目を実行したあとの値を入れてください。変わらない変数は、 そのままの値を入れます。まだ値が入っていない変数は「—」と入れます。