読み方：さいきかんすう

概要

再帰関数（recursive function）とは、関数の定義の中に、その関数の呼び出しが含まれるもの。そのような自身が自身を呼び出すような関数呼び出しを「再帰呼び出し」という。

多くのプログラミング言語には、まとまったコードのかたまりに名前を付け、外部からパラメータ（引数）を渡して繰り返し呼び出すことができる「関数」（function）の仕組みがあるが、その処理を記述したコードの中で、自らを呼び出すコードが含まれるようなものを再帰関数という。

例えば、階乗の計算 n!=n×（n-1）! やフィボナッチ数列 F_n+2=F_n+1+F_n のように、定義や算法にある種の再帰的な構造が含まれている場合、これをシンプルなコードに書き表すことができる。関数型言語では繰り返し処理を原則として再帰関数として表す。

現代的なプログラミング言語のほとんどは再帰関数の定義・実行が可能な仕様となっているが、再帰関数を記述する際には、関数が終了しないまま何度も新たに呼び出されても、内部の状態が壊れないよう配慮された「リエントラント」（再入可能）な構造になっている必要がある。

また、関数の中で自らを呼び出す箇所の手前に、脱出条件を満たしたら新たに再帰呼び出しせずに関数を終了する条件分岐を記述しなければならない。脱出コードが無かったり条件が誤っていると、無限に自身を呼び出し続けて終了しない（実際にはスタックを使い果たして異常終了する）プログラムとなってしまう。