関数：まとめと挑戦課題

要約

このレッスンは、関数を扱うコースの第 5 単元を締めくくる。関数の宣言から再帰へ至る概念の連鎖を、コールスタック、契約、引数の渡し方、変数のスコープと生存期間、段階的詳細化による設計を経由して組み立て直す。そのうちどの言語でも通用することと C++ に固有のこととを分ける。単元の未定義動作を集め、コンパイラが警告すること、サニタイザが止めること、誰も指摘しないことを添える。まとめテストで導入テストの技能を繰り返す。そして、単元全体を組み合わせる六つの挑戦課題で終わる。

学習目標

問題を関数に分解し、それぞれにインタフェースと契約（事前条件と事後条件）を与え、別々にテストする。
各仮引数の渡し方と結果の返し方を選び、その選択を正当化する。
問題を再帰で解き、その正しさを帰納法で、その停止を減少する尺度で証明し、呼び出しの回数でそのコストを見積もる。
単元の未定義動作（return のない経路、ダングリング参照、オーバーフローする結果、尽きたスタック）を見分け、それのないプログラムに書き直す。
単元で学んだことのうち、どの言語でも通用することと C++ に固有のこととを分ける。

単元で達成したこと

この単元は、問題を名前のついた部分に分解し、それぞれにインタフェースと契約を与えること、そして問題を再帰で解くことを教えようとした。この目的は、導入が既知と宣言したことだけに基づいて果たされた。第 4 単元のループとその不変条件と変量、レッスン 1.1 の仕様、そして第 2 単元のメモリのモデルである。コピーしたループが間違った数の約数を足していた友愛数のプログラムは、今では一つの関数だけで書かれ、その関数は契約に照らして一度だけ検証される。

関数

レッスン関数は、関数を宣言し、定義し、呼び出すことを教え、三つの時点を分けた。コンパイル時には、各呼び出しがそれより前にある宣言に照らして検査される。リンク時には、定義が探される。実行時には、実引数が計算され、コールスタックにフレームが作られ、制御が本体へ移る。void でない関数が return なしに末尾に達することは未定義動作であることを示し、最後に契約、すなわち事前条件と事後条件を扱った。契約は呼び出し側と関数のあいだで責任を分け合う。

引数とスコープ

レッスン引数とスコープは、データがどの道を通って入り、結果がどの道を通って出るかを調べた。値渡しの仮引数はコピーであり、参照渡しの仮引数は呼び出し側の区画の第二の名前であり、const 参照はコピーせずに読む。ここから選択の規則（小さいものは値、読むだけの大きいものは const 参照、変更そのものが目的のときだけ参照）が導かれ、複数の結果には std::pair と std::tuple を構造化束縛とともに使う。名前のスコープ（テキストの性質）と変数の生存期間（実行の性質）を区別し、自分の区画より長く生きる参照で終わった。

関数による設計

レッスン関数による設計は、段階的詳細化によって、どの関数を書くかを決める方法を教えた。宣言しただけの関数を呼び出す短い main を書き、それぞれへ降りていく。そうすると分解は木として描ける。よいインタフェースの基準と「一つの関数に一つの仕事」という規則を、その兆候（名前の中の接続詞、一画面に収まらない関数、フラグ）とグローバル変数のような隠れた作用とともに定め、オーバーロードをその優先順位と曖昧な呼び出しとともに紹介し、第 4 単元のアルゴリズムを別々にテストした関数として書き直した。

再帰

レッスン再帰は、関数が問題のより小さな事例を解くために自分自身を呼び出せることを教えた。より小さな呼び出しを正しいと仮定して帰納法で正しさを証明し、減少する自然数の尺度で停止を証明した。積み重なっては取り除かれるフレームをスタックで追い、スタックがどのように尽きるかを示した。結果の型がスタックよりずっと早くオーバーフローすることに注意を促した。そして、フィボナッチ数の再帰版と反復版を比べた。 $2\,692\,537$ 回の呼び出しに対して 29 回の加算である（ $F_{30}$ の場合）。