Part14: 再帰

ダイヤ「祝!」
花丸「果南さんの出番!(8話)」
果南「出番があっただけで祝われるってのも、ちょっとなあ・・・」
ダイヤ「いよいよ闇を抱えた真のヒロインという感じが出てきましたわね」
果南「いや、ヒロインって・・・そんな柄じゃ」
ダイヤ「前評判ではちょろそうだった果南ルートが最難関になるとは予想もしませんでしたわ」
花丸「でも3年組の1年生時代は楽しそうずら。ダイヤさんもあんなにはしゃいじゃって」
ダイヤ「!? あ、あれは・・・そう、若気の至りというやつですわ!」


ダイヤ「さて、今回は繰り返しの話をしますわ」
果南「これでプログラミングの3要素が揃うね」
ダイヤ「逐次・判断・繰り返し・・・ここまでで学ぶ内容で、基本的にはあらゆるアルゴリズムを表現できるようになりますわね」
花丸「なんか成長した気がするずら」
ダイヤ「Schemeの繰り返し処理は、専用の構文もあるにはあるのですが、再帰というテクニックを使うのが一般的なようです。簡単な例を見てみますわ」

ダイヤ「指定した回数”しいたけ”を結合した文字列を返す手続きshiitakeを・・・」
花丸「梨子さんが見たら泣くずら」
ダイヤ「ああなるとショック療法も必要ですわ。ともかく、このshiitakeの中身を見ていきます」

ダイヤ「shiitakeの中では1回が指定された場合とそれ以外が指定された場合に分岐していて、まず1回の場合は簡単ですわね?」
花丸「評価結果がしいたけになって終わりずら」
ダイヤ「ではそれ以外の場合は?」
果南「回数分しいたけを結合するからstring-appendで、えーと、ここでまたshiitakeを呼び出してる?」
ダイヤ「それが再帰です。手続きの中で自分自身を呼び出すことですわ」
果南「(shiitake 3)で始まったから、1を引いて(shiitake 2)を実行して、返ってきた結果にしいたけを結合してる、と」
花丸「そうすると、(shiitake 2)の中でも(shiitake 1)を実行することになるずら」
果南「(shiitake 1)の結果ってしいたけだよね。だとすると(shiitake 2)の結果は(shiitake 1)の結果にしいたけを結合してしいたけしいたけ」
花丸「じゃあ(shiitake 3)(shiitake 2)の結果にしいたけを結合してしいたけしいたけしいたけずら!」
ダイヤ「正解、ですわ」
果南「しいたけって単語がゲシュタルト崩壊起こしてきたよ・・・」

  1. (shiitake 3)を呼び出す
  2. (shiitake 3)の中で(shiitake 2)を呼び出す
  3. (shiitake 2)の中で(shiitake 1)を呼び出す
  4. (shiitake 1)の結果はしいたけなのでしいたけを返す
  5. (shiitake 2)(shiitake 1)の結果にしいたけを結合してしいたけしいたけを返す
  6. (shiitake 3)(shiitake 2)の結果にしいたけを結合してしいたけしいたけしいたけを返す

ダイヤ「このような内部動作となります。nの値を大きくした場合はこの呼び出し階層が深くなるだけですわ」
果南「なるほど、ぐるぐる回すイメージじゃなくて穴掘ってく感じか」


ダイヤ「次に末尾再帰というテクニックを紹介します」
花丸「末尾?」
ダイヤ「ある手続きから別の手続きを呼び出す場合、呼び出し元の手続きが利用していた変数の値などはスタックと呼ばれる領域に待避され、処理が戻ってきたら再びスタックから戻す、という動作をします」
果南「手続き呼び出すにもコストがかかるって話?」
ダイヤ「そんなところです。1回1回は微々たるものでも、何千回何万回と再帰を繰り返すとパフォーマンスに影響が出たり、環境によってはスタックが溢れたりしますわ」
花丸「そんなにたくさん処理するところはまだ想像つかないけど・・・でも、処理できなくなっちゃうのは困るずら」
ダイヤ「そこで末尾再帰という、スタックを使わない再帰の書き方があるのです」

ダイヤ「ポイントは2つ。再帰呼び出しを手続きの最後に書くこと、結果を引数に含めてしまうことです」
果南「それでshiitake2の呼び出しが一番外側に来るようにして、結果はtmpに入れて受け渡してると」
花丸「shiitake2の最後がshiitake2の呼び出しで、そこまでの値を引数で渡すんだったら、途中経過をスタックに残しておく必要なくなるずら」
ダイヤ「Schemeには末尾再帰最適化という仕組みがあって、この書き方をすると他の言語のループと同じようにオーバーヘッドのない繰り返しが書けますわ」


ダイヤ「最後に名前付きletという記法について見ておきますわ」

ダイヤ「letはローカル変数のところで出てきましたわね。ここでは、letの式にloopという名前を付けて、それを呼び出すことで繰り返しを行っています」
果南「これは何が嬉しいの?」
ダイヤ「ローカルな再帰関数が定義できる、といったところでしょうか。Schemeではよく使われる書き方のようですわ」


ダイヤ「では次回は、ファイル入出力をやってみますわ」
花丸「やっと実用性が出てきたずら」
果南「$ gosh shiitake.scm > ~/shiitake.txt
ダイヤ「そういうことではありませんわ・・・」


LINEで送る
Pocket


返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です