読み方 ： さいきかんすう

再帰関数 【recursive function】

概要

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

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

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

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

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

(2023.10.22更新)

他の用語辞典による「再帰関数」の解説 （外部サイト）

資格試験などの「再帰関数」の出題履歴

▼ 基本情報技術者試験
【令5修1 問8】 次の関数 f(n，k) がある。f(4，2) の値は幾らか。。
【令4修12 問10】 自然数nに対して，次のとおり再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。　f(n)：if n≦1 then return 1 else return n+f(n-1)。
【令4修7 問10】 整数x，y（x＞y≧0）に対して，次のように定義された関数F（x，y）がある。F（231，15）の値は幾らか。ここで，x mod yはxをyで割った余りである。
【令4修6 問7】 2分木の各ノードがもつ記号を出力する再帰的なプログラムProc（n）の定義は，次のとおりである。このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。
【令4修1 問9】 再帰的に定義された手続 proc で，proc（5）を実行したとき，印字される数字を順番に並べたものはどれか。proc（n）　n=0 ならば戻る　そうでなければ　{　　nを印字する　　proc（n-1）を呼び出す　　nを印字する　}　を実行して戻る。
【令3修7 問10】 nの階乗を再帰的に計算する関数 F(n) の定義において，aに入れるべき式はどれか。ここで，nは非負の整数とする。　n＞0のとき，F(n)＝[　a　]　n＝0のとき，F(n)＝1。
【令3修6 問9】 関数 f(x，y) が次のとおり定義されているとき，f(775，527) の値は幾らか。ここで，x mod y はxをyで割った余りを返す。
【令2修12 問9】 整数x，y（x＞y≧0）に対して，次のように定義された関数F（x，y）がある。F（231，15）の値は幾らか。ここで，x mod yはxをyで割った余りである。
【令2修7 問7】 2分木の各ノードがもつ記号を出力する再帰的なプログラムProc（n）の定義は，次のとおりである。このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。
【令1秋 問11】 自然数nに対して，次のとおり再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。　f(n)：if n≦1 then return 1 else return n+f(n-1)。
【令1修7 問8】 関数 f(x，y) が次のとおり定義されているとき，f(775，527) の値は幾らか。ここで，x mod y はxをyで割った余りを返す。
【令1修6 問7】 nの階乗を再帰的に計算する関数 F(n) の定義において，aに入れるべき式はどれか。ここで，nは非負の整数とする。　n＞0のとき，F(n)＝[　a　]　n＝0のとき，F(n)＝1。
【平31修1 問6】 次の関数 f(n，k) がある。f(4，2) の値は幾らか。。
【平30修12 問5】 整数x，y（x＞y≧0）に対して，次のように定義された関数F（x，y）がある。F（231，15）の値は幾らか。ここで，x mod yはxをyで割った余りである。
【平30修7 問7】 自然数nに対して，次のとおり再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。　f(n)：if n≦1 then return 1 else return n+f(n-1)。
【平30修6 問5】 2分木の各ノードがもつ記号を出力する再帰的なプログラムProc（n）の定義は，次のとおりである。このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。
【平30修1 問7】 再帰的に定義された手続 proc で，proc（5）を実行したとき，印字される数字を順番に並べたものはどれか。proc（n）　n=0 ならば戻る　そうでなければ　{　　nを印字する　　proc（n-1）を呼び出す　　nを印字する　}　を実行して戻る。
【平29修12 問8】 nの階乗を再帰的に計算する関数 F(n) の定義において，aに入れるべき式はどれか。ここで，nは非負の整数とする。　n＞0のとき，F(n)＝[　a　]　n＝0のとき，F(n)＝1。
【平29修6 問7】 次の関数 f(n，k) がある。f(4，2) の値は幾らか。。
【平29春 問6】 関数 f(x，y) が次のとおり定義されているとき，f(775，527) の値は幾らか。ここで，x mod y はxをyで割った余りを返す。
【平28修12 問5】 2分木の各ノードがもつ記号を出力する再帰的なプログラムProc（n）の定義は，次のとおりである。このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。
【平28秋 問7】 整数x，y（x＞y≧0）に対して，次のように定義された関数F（x，y）がある。F（231，15）の値は幾らか。ここで，x mod yはxをyで割った余りである。
【平28春 問7】 nの階乗を再帰的に計算する関数 F(n) の定義において，aに入れるべき式はどれか。ここで，nは非負の整数とする。　n＞0のとき，F(n)＝[　a　]　n＝0のとき，F(n)＝1。
【平27秋 問8】 自然数nに対して，次のとおり再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。　f(n)：if n≦1 then return 1 else return n+f(n-1)。
【平26修12 問7】 整数x，y（x＞y≧0）に対して，次のように定義された関数F（x，y）がある。F（231，15）の値は幾らか。ここで，x mod yはxをyで割った余りである。
【平26秋 問7】 次の関数 f(n，k) がある。f(4，2) の値は幾らか。。
【平26修7 問8】 関数 f(x，y) が次のとおり定義されているとき，f(775，527) の値は幾らか。ここで，x mod y はxをyで割った余りを返す。
【平26春 問6】 2分木の各ノードがもつ記号を出力する再帰的なプログラムProc（n）の定義は，次のとおりである。このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。
【平25修12 問7】 nの階乗を再帰的に計算する関数 F(n) の定義において，aに入れるべき式はどれか。ここで，nは非負の整数とする。　n＞0のとき，F(n)＝[　a　]　n＝0のとき，F(n)＝1。
【平24秋 問7】 n!の値を，次の関数 F(n) によって計算する。乗算の回数を表す式はどれか。。
【平23修12 問7】 次の関数 f(n，k) がある。f(4，2) の値は幾らか。。
【平23春 問6】 関数 f(x，y) が次のとおり定義されているとき，f(775，527) の値は幾らか。ここで，x mod y はxをyで割った余りを返す。
【平21修12 問8】 次の関数 f(n，k) がある。f(4，2) の値は幾らか。。
【平21春 問8】 自然数nに対して，次のとおり再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。　f(n)：if n≦1 then return 1 else return n+f(n-1)。