再帰
再帰（recursion，リカージョン）とは，自分から自分を呼び出すこと。
フィボナッチ数列は $ a_1 = 1, $ a_2 = 1, $ a_n = a_{n-1} + a_{n-2} で定義される。$ n を与えて $ a_n を求める関数 fib(n) を定義しよう。簡単のため，$ n < 1 のとき $ a_n = 1 とした。
code:fib.c
#include <stdio.h>
int fib(int n)
{
if (n < 3) {
return 1;
} else {
return fib(n-1) + fib(n-2);
}
}
int main(void)
{
int n;
printf("n? "); scanf("%d", &n);
printf("fib(%d) = %d\n", n, fib(n));
return 0;
}
fib() の中で fib() を呼び出している。これが再帰の例である。
再起は必ずしも効率的ではない。上のプログラムで fib() がどのように呼び出されているか調べてみよう。
code:fib2.c
#include <stdio.h>
int count = 0;
int fib(int n)
{
printf("fib(%d)\n", n);
count++;
if (n < 3) {
return 1;
} else {
return fib(n-1) + fib(n-2);
}
}
int main(void)
{
int n;
printf("n? "); scanf("%d", &n);
printf("fib(%d) = %d\n", n, fib(n));
printf("count = %d\n", count);
return 0;
}
これで fib(10) を計算すると，fib() が109回呼び出されていることがわかる。