相互再帰関数

ある関数群のそれぞれの関数がその本体からその関数群の関数を呼び出している時、 その関数群は相互再帰的に定義されています。 相互再帰関数は実際の場面で一般に使われます。

例として、P を次のような自然数の関数とします:

• P(0) = 1

• P(n+1) = 1 + (i の範囲が 1 から n までの時、i と P(i) の積の合計)

• P(0) = 1

• P(n+1) = 1 + Q(n)

• Q(0) = 0

• Q(n+1) = Q(n) + (n+1) * P(n+1)

fun P (n:int): int = if n > 0 then 1 + Q(n-1) else 1
and Q (n:int): int = if n > 0 then Q(n-1) + n * P(n) else 0