再帰
もう1つの例は、以下のように帰納または再帰を用いて定義される証明手続き (Proof procedure) の観点から定義される公理体系内のあらゆる「証明可能な」命題の集合である。
ある命題が公理であるならば、それは証明可能な命題である。
ある命題が推論規則によって真に到達可能な命題から導出できるなら、それは証明可能な命題である。
証明可能な命題の集合は、これらの条件を満たす命題の最小の集合である。
連結リストや木構造は、要素(ノード)の型の中にその要素型自身への参照(自己参照)が存在するようなデータ型を用いて実現される。これは再帰的データ構造(再帰データ型)である。再帰的データ構造の探索には、再帰呼び出しを使うことが多い。
下記は Java での例。Tree のクラス定義の中で Tree を使用している。
言語学者ノーム・チョムスキーらは、言語において適格文の数に上限がなく、適格文の長さにも上限がないことは、自然言語での再帰の結果として説明可能だと論じている。
これは、文章など統語範疇での再帰的定義という観点から理解可能である。文章では、動詞の補語などが別の文章という構造を持つことができる。「ドロシーは魔女が危険だと考えている」には「魔女は危険だ」の一文がより大きな文章に含まれている。それゆえ文章とは、名詞句と動詞に別の文章を含みうる構造を持つものだと、再帰的に(非常に大まかだが)定義することができる。
これは、文章が任意の長さになり得ることも意味する。例えば、英語だと関係代名詞の"that"を使うことによって、
"Dorothy thinks that Toto suspects that Tin Man said that..."
と再帰的に文を継ぎ足すことが可能である。
手続きや関数といった概念をもつプログラミング言語では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。これを再帰呼出しといい、階乗計算やフィボナッチ数列のように、本来再帰的な構造をもつアルゴリズム(再帰的アルゴリズム)を記述するのに適している。
複数の手続き/関数が互いに相手を呼ぶ場合も、広い意味での再帰呼出し(相互再帰)である。C言語での例:
処理を中断・終了する基底条件が必ず1つは必要で、その部分が誤っていると、無限に関数を呼び出し続けることがある(暴走)。無限再帰に陥ると、スタックオーバーフローによりプログラムが異常終了したり、システムが停止したりする原因となる。