再帰の問い方2009

いきなりですが，空欄適語問題です．[ 1 ]〜[ 3 ]に入る語句を，考えてみてください．

関数の内部で自分自身を呼び出すことを [ 1 ] 呼び出しといい， [ 1 ] 的に定義されたものに対して使用すると効果的である．たとえば，カウントアップとカウントダウンを行う以下の2つの関数は，いずれも [ 1 ] 呼び出しを行っている．
void countup(int x)
{
  printf("x = %d\n", x);
  if (x > 0) {
    countup(x - 1);
  }
}

void countdown(int x)
{
  if (x > 0) {
    countdown(x - 1);
  }
  printf("x = %d\n", x);
}
countdown(3) を呼び出したとき，まず仮引数 x のオブジェクトが作られ，そこに3を代入する． if の条件は真なので， countdown(x - 1) すなわち countdown(2) を呼び出す．ここで [ 1 ] 呼び出しがなされる．
次に countdown(2) の処理をするために，仮引数 x のオブジェクトが作られ，2を代入する．同様にして引数を1ずつ減らしながら [ 1 ] 呼び出しをしていくが， countdown(0) を処理する中では， if の条件が偽となるため countdown(-1) は呼び出さず， printf 関数により，現在の x の値すなわち0を出力する． countdown(0) の処理が終わると，0が代入された x のオブジェクトは破棄される．
countdown(1) の処理中， countdown(0) を呼び出した直後に制御が戻り， x の値すなわち1を出力する．同様に，関数処理を行っていく．
[ 1 ] 呼び出しをする関数が意図どおりに動作するのは，[ 2 ] からである．定義した2つの関数について， [ 1 ] 呼び出しと値の出力の順序を変えることで，カウントアップとカウントダウンという正反対の結果になるのは興味深い．ただし，これらの関数は，[ 3 ]という点で不適切である．

タイトルにあるとおり，[ 1 ]に入るのは「再帰」です．今年度の授業では，12月14日に取り上げる予定です．[ 2 ]と[ 3 ]は，単語ではなく少々長い（といっても20字程度の）記述をしてもらいますが，答えはまたあとで．
あることがきっかけで，『解きながら学ぶC言語』を見せてもらいました．本棚にあった『新版明解C言語入門編』と併せて，ざっと読みました．
帯に「999問を解いて，C言語力を身につけよう」と書かれているとおり，問題は充実しています．まあ，学生が999問を自習するよりも，教員が問題を作る際の元ネタに有用そうです．malloc系関数がないことを除けば，私の担当科目の内容をほぼカバーしています．逆に，私の授業で触れていないトピックとして，time関数やstruct tm型などが取り上げられています．
プログラム例の中では，unsigned型の各整数を2進数で表示するもの（p.161, 明解p.163, pp.168-170）が興味深いです．整数xの中で1になっているビット数を返す関数int count_bits(unsigned);を定義しておけば，unsigned型のビット数はcount_bits(~0U)で求められるとは．
しかしまあ，2進表示に限れば，関数をあえて定義することなく，求められるので，授業のサンプルプログラムを継続して使うことにします．
以下しばらくは，この本を読んで，学科の教育上まずいと感じたところを書いていきます．私の教え方を，変えるべきなのかもしれませんが．
書籍全体を通じて，入力をとる方法について，言及が少ないのが気になります．ユーザからの入力を得る方法は，大部分がscanfでした*1．さらに見直すと，argc, argvを使用していません（明解も）．とはいっても，教科書の一つ，『Cプログラミング入門以前』も事情はそれほど変わらず，argcとargvは用語としてのみ出現しています．
argcとargvは，入力をとる実用的な方法の一つであることと，ポインタ・配列・文字列がうまく組み合わさった例なので，授業ではポインタの回で，取り上げています（今年度も，すでに説明しました）．それと，何年か前までは，「入力の与え方」として，「ハードコーディング」「コマンドライン引数から」「標準入力から」「ファイルから」の4通りとそのメリットとデメリットを，何枚かのスライドで説明してから，ファイルなどの入出力処理を解説していたものですが，ここ最近は，主に時間の都合で，入力の与え方の話題を言えないでいます．大事なんですけどね．まあ，授業の工夫はまた考えるとします．
本に戻って，引っかかった小さな表現が，「仮引数を受け取る」．p.130に『( )で囲まれた部分は，この関数が受け取る仮引数(parameter)の宣言であり』と書かれています．『仮引数を受け取らない関数』(p.137)という小見出しもあります．
私の認識では，仮引数は関数定義に付随するものであり，「この関数は，ナントカ型のコレコレを引数にとり，ナニナニを行う／返す」というのが基本形です．ここの「とり」は英語でいうtakeであり，receiveではありません．関数呼び出しの際に引数の授受が行われますが，呼び出し側と関数側の引数を区別するため，前者を実引数(argument)，後者を仮引数(parameter)と呼び分けます．
あともう一つ，これは冒頭の空欄適語問題の [ 2 ] にも関わるのですが，なぜ再帰呼び出しがうまくいくかの説明に，不満を覚えました．

なお，再帰的な呼出しが“自分自身の関数”を呼び出すと説明されることがありますが，誤解しないでください．“自分自身の関数”を呼び出すのではなく，あくまでも“自分自身と同じ関数”を別途呼び出すと考えなければなりません．だって，本当に自分自身を呼び出すのだったら，えんえんと自分自身を呼び続けることになるでしょう!
(解きながら学ぶC言語, p.185)

明解pp.194-195では，多色刷りを利用して，再帰呼び出しの各関数が物理的に異なるように描かれています．
これらの本の考え方をもとに，[ 2 ] の解答に「自分自身と同じ関数を別途呼び出す」と書いたら…私の採点では，×をつけざるを得ません．
「自分自身と同じ関数を別途呼び出す」ということは，関数AがA自身を呼び出すのと，関数Bがそれと異なる関数Cを呼び出すのを，区別するということです．関数名だけでなく引数を割り当てて，「countup(3)が呼び出された処理中にcountup(2)を呼び出すのと，main関数からcountup(2)を呼び出すのは，区別しないといけない」と書いてみて，この主張は通るでしょうか．不自然，不適切です．そしてCの規格でもコンパイラの構成法でも，別に扱うというのを見聞きしたことがありません*2．
『本当に自分自身を呼び出すのだったら，えんえんと自分自身を呼び続けることになるでしょう』については，その反証として，再帰呼び出しで無限ループになるコード*3が容易に思い浮かびます．
再帰呼び出しをして，無限ループにならないのは，再帰呼び出しが持つメカニズムではなく，再帰関数の中で，冒頭の例題であれば「if (x > 0)」とあるように，再帰呼び出しをする／しないための条件判定を入れているからです*4．
ところで，最初の問題は，今年1月28日の授業で出した，プレ試験問題の一部です．採点しませんし，そもそも授業中に正解を言いました．[ 2 ]の解答として，以下のいずれかであれば○でしょう．

関数内の自動変数が，関数呼び出しごとに生成される
自動変数や関数の呼び出し位置をスタックで管理している
再帰呼び出しをしなくするための条件判定がある

[ 3 ]はプログラミングの問題だけでなく日本語の読解も含まれています．答えてほしかったのは

関数名と処理内容が合っていない

です．どんな出力をするかに着目すれば，countupとcountdownが反対だと分かりますし，こう答案を書く学生は，再帰呼び出しによってどのように処理が進むか，分かっていると言っていいでしょう．ただ，再帰と言えばということで

再帰呼び出しをしない関数のほうが効率よく処理する

でも○です．

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．

関連