再帰
関数は自身を再帰的に定義する場合がある。とりわけ漸化式が数列を再帰的に定める数式であり、その身近な例が F ( n ) = F ( n − 1 ) + F ( n − 2 ) {\displaystyle F(n)=F(n-1)+F(n-2)} というフィボナッチ数列である。こうした漸化式による定義が成立する場合、その数式は再帰を用いずに定義された基底値 (フィボナッチの場合 F ( 0 ) = 0 {\displaystyle F(0)=0} と F ( 1 ) = 1 {\displaystyle F(1)=1} )に帰着できる必要がある。また、漸化式の再帰関係を解いた場合は非再帰的な定義(一般項)を得ることが可能である。
有名な再帰関数にアッカーマン関数があるが、これは原始再帰関数よりも早く増大して巨大数を生み出すため、再帰を使わずに一般項を簡単な式で表すことが出来ない点がフィボナッチ数列とは異なる。