多くの数学的公理は、再帰を用いた法則に基づいている。例えば、ペアノの公理による自然数の正式な定義は「ゼロは自然数であり、各自然数には後続数があり、これも自然数である」と記述されうる。この基底段階および再帰を用いた法則によって、全ての自然数の集合を生成できる。
他にも再帰を用いて定義されている数学的対象としては、関数の漸化式、集合のカントール集合、フラクタル分野、プログラミング言語における階乗、などがある。
言語.
言語学者ノーム・チョムスキーらは、言語において適格文の数に上限がなく、適格文の長さにも上限がないことは、自然言語での再帰の結果として説明可能だと論じている。
これは、文章など統語範疇での再帰的定義という観点から理解可能である。文章では、動詞の補語などが別の文章という構造を持つことができる。「ドロシーは魔女が危険だと考えている」には「魔女は危険だ」の一文がより大きな文章に含まれている。それゆえ文章とは、名詞句と動詞に別の文章を含みうる構造を持つものだと、再帰的に（非常に大まかだが）定義することができる。
と再帰的に文を継ぎ足すことが可能である。再帰的に定義できうる文章の他にも多くの構造があり、別の品詞に文章を組み込む方法も沢山ある（例えば修飾語を文章形式にする）。長い歳月を経て、言語には一般的にこの種の分析で順応性があることが証明されている。
再帰を使った洒落.
たまに再帰は、計算機科学・プログラミング等の書物で、ジョークとして掲載される場合がある。そうした本では概して循環定義や自己参照が付されており、次のような馬鹿らしい項目が用語集として載っていることも珍しくない。
数学.
再帰的定義.
例: 自然数.
再帰的に定義された集合の標準例が、自然数である。
例: 証明手続き.
有限分割規則.
関数での再帰.
有名な再帰関数にアッカーマン関数があるが、これは原始再帰関数よりも早く増大して巨大数を生み出すため、再帰を使わずに一般項を簡単な式で表すことが出来ない点がフィボナッチ数列とは異なる。
再帰的定義を含む証明.
前節のような、再帰的定義がされた集合や関数に対して複数場合分けによる証明の標準的な手法を適用すると、構造的帰納法が得られる。これは数理論理学とコンピュータサイエンスで証明を導出するのに広く使用されている数学的帰納法の強力な一般化である。