構造的帰納法
以下の length 関数と ++ 演算子は、構造的に再帰した関数の例である。
例として線型リストの構造を考える。通常は半順序 '<' を、リスト L, M に対して「L が M の尾部(tail)であるときに L < M」と定める(厳密にはその推移閉包をとる)。この順序において、空のリスト [] は唯一の極小元である。リストの元 l に対する述語 P(l) の構造的帰納法による証明は、次の2つの部分証明からなる。
P([]) が真である。
あるリスト L について P(L) が真であり、L がリスト M の尾部であると仮定したとき、P(M) も真である。
結局のところ、関数や構造の定義の仕方によっては、基礎ケースが2つ以上あったり、帰納ケースが2つ以上あったりする。それゆえ、それらのケースにおいて、ある性質 P(l) の構造的帰納法による証明は次の2つからなる。
各基礎ケース BC に対して P(BC) を証明する。
構造のある要素 I について P(I) が真であり、M が I にいずれかの再帰ルールを適用して得られるなら、P(M) もまた真である、ということを証明する。