再帰定義

再帰定義とは、関数を定義する際に自分自身を呼び出すような定義をする方法です。これを使うと、繰り返しを伴うような処理も定義することができます。

再帰定義の簡単な例

再帰定義の簡単な例を以下に示します。

f(n)=(n >= 1 ? f(n-1)+floor(n) : 0.0)

上のf(n)の定義の右辺で「自分自身」であるf(n-1)が呼び出されています。このような定義方法を再帰定義と呼ぶのです。なお、再帰定義は、通常は三項演算子? :とともに使われます。これは、無限ループに陥ってしまうのを防ぐためです。

次に、上記例がどのような値を返す関数かを考えてみましょう。まず、nが1より小さい場合はf(n)は常にゼロです。もしnが1以上である場合は複雑です。例えばn=3の場合を考えてみましょう。上記定義によると、

f(3) = f(2)+3

です。ここでさらに未知のf(2)の値を知らねばなりません。再び上記定義を使って、

f(2) = f(1)+2

です。同様に

f(1) = f(0)+1

となります。上で述べたように右辺のf(0)はゼロですので、ようやく未知の値はなくなりました。まとめると、結局

f(3) = f(2)+3 = f(1)+2+3 = f(0)+1+2+3 = 0+1+2+3 = 6

となります。任意のnについても同様に考えることができ、f(n)は0からnを超えない整数までの和を返す関数ということになります。

これは公式0+1+2+...+n = n*(n+1)/2を利用して以下のスクリプトで確かめられます。

f(n)=(n >= 1 ? f(n-1)+floor(n) : 0.0) # 0+1+2+...+n = n*(n+1)/2

set samples 1000
set xrange [0:10]
plot f(x), x*(x+1)/2.0

このスクリプトの実行例は下に示す通りで、xが整数のところでf(x)とx*(x+1)/2.0が一致していることが分かります。

再帰定義の注意点

上のスクリプトでxrangeの上限を大きくしすぎるとgnuplotが「recursion depth limit exceeded」というエラーを返します。これは、再帰定義の呼び出しの繰り返し回数が上限値を超えてしまったということです。例えば、手元のgnuplot4.4.3では上限が101を超えるとエラーになりますが、この値はgnuplotのバージョン等によって異なるようです。

再帰定義の応用例

gnuplotにおいては、再帰定義を用いることで、例えば積分関数を定義したり、関数の級数展開をしたりすることができます。また、便利な文字列関数でも再帰定義を利用しています。