この用語はまだ監査を通っていません（未確認）。
構造帰納法
こうぞうきのうほう 1対1で対応structural induction
名詞 ・書き言葉・答案
定義
再帰的に定義された集合（木や文字列、式など）のすべての要素がある性質をもつことを示す帰納法。基本の要素で成り立ち、新しい要素を作る各規則で性質が引き継がれることを示す。
A form of induction for recursively defined sets such as trees, strings, or expressions. You show that the property holds for the basic elements and is preserved by each rule that builds new elements.
例文
話し言葉 Strings are defined recursively, so we'll use structural induction: check the empty string, then show the property survives when you add one more character. 文字列は再帰的に定義されているから、構造帰納法を使おう。空の文字列で確かめて、1 文字付け足しても性質が保たれることを示す。
書き言葉・答案 Prove by structural induction that every full binary tree with n leaves has n − 1 internal vertices. 構造帰納法を用いて、葉が n 個の全二分木の内部頂点はちょうど n − 1 個であることを証明せよ。
言い間違えやすいところ
- 自然数についての普通の帰納法は、「0 と、n から n + 1 を作る規則」で定義された集合に対する構造帰納法の特別な場合とみなせる。
- 日本の高校数学では扱わず、大学の離散数学や情報科学で出てくる。
- 用例コーパスで structural induction は書き言葉（MIT の講義ノート）にだけ出てきて、話し言葉には出てこない。