フィボナッチ数列を返す関数

フィボナッチ数列は漸化式 \[ f_{n+2} = f_{n+1} + f_n, \quad (f_0=0,f_1=1) \] で定義される数列である。 今回は指定した個数だけ、フィボナッチ数列を返す関数を作成する。

コード例1

漸化式を用いて、再帰的に定義する。

#include <stdio.h>
int fibo(int n);
int main()
{
	int i;
	for (i = 0; i < 21; i++)
	{
		printf("fibo(%2d) = %10d \n", i, fibo(i));
	}
}
int fibo(int n) {
	if (n == 0) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	return fibo(n - 1) + fibo(n - 2);
}

実行結果

fibo( 0) =          0
fibo( 1) =          1
fibo( 2) =          1
fibo( 3) =          2
fibo( 4) =          3
fibo( 5) =          5
fibo( 6) =          8
fibo( 7) =         13
fibo( 8) =         21
fibo( 9) =         34
fibo(10) =         55
fibo(11) =         89
fibo(12) =        144
fibo(13) =        233
fibo(14) =        377
fibo(15) =        610
fibo(16) =        987
fibo(17) =       1597
fibo(18) =       2584
fibo(19) =       4181
fibo(20) =       6765

解説

再帰を用いると、直感的でわかりやすいが、数値が大きくなると非常に遅くなる。

コード例2

再帰的に関数を呼び出さない方法を考える。

#include <stdio.h>
int fibo(int n);
int main()
{
	int i;
	for (i = 0; i < 21; i++)
	{
		printf("fibo(%2d) = %10d \n", i, fibo(i));
	}
}
int fibo(int n) {
	int a = 0;
	int b = 1;
	int c;
	if (n == 0) {
		return 0;
	}
	int i;
	for (i = 0; i < n; i++) {
		c = a + b;
		b = a;
		a = c;
	}
	return c;
}

実行結果

fibo( 0) =          0
fibo( 1) =          1
fibo( 2) =          1
fibo( 3) =          2
fibo( 4) =          3
fibo( 5) =          5
fibo( 6) =          8
fibo( 7) =         13
fibo( 8) =         21
fibo( 9) =         34
fibo(10) =         55
fibo(11) =         89
fibo(12) =        144
fibo(13) =        233
fibo(14) =        377
fibo(15) =        610
fibo(16) =        987
fibo(17) =       1597
fibo(18) =       2584
fibo(19) =       4181
fibo(20) =       6765

解説

若干わかりづらくなったが、こちらのほうが処理が速い。

コード例3

指定した個数のフィボナッチ数列を得る関数を作成する。

#include <stdio.h>
#include <stdlib.h>
int* getFibonacciSequence(int max);
int main()
{
	int max = 21;
	int* g = getFibonacciSequence(max);
	int i;
	for (i = 0; i < max; i++)
	{
		printf("fibo(%2d) = %10d \n", i, g[i]);
	}
	free(g);
}

int* getFibonacciSequence(int max) {
	if (max <= 0) {
		exit(1);
	}
	int* fi = (int*)malloc(sizeof(int) * max);
	if (fi == NULL) {
		exit(1);
	}
	if (max == 1) {
		fi[0] = 0;
		return fi;
	}
	if (max == 2) {
		fi[0] = 0;
		fi[1] = 1;
		return fi;
	}
	int i;
	fi[0] = 0;
	fi[1] = 1;
	for (i = 2; i < max; i++)
	{
		fi[i] = fi[i - 1] + fi[i - 2];
	}
	return fi;
}

実行結果

fibo( 0) =          0
fibo( 1) =          1
fibo( 2) =          1
fibo( 3) =          2
fibo( 4) =          3
fibo( 5) =          5
fibo( 6) =          8
fibo( 7) =         13
fibo( 8) =         21
fibo( 9) =         34
fibo(10) =         55
fibo(11) =         89
fibo(12) =        144
fibo(13) =        233
fibo(14) =        377
fibo(15) =        610
fibo(16) =        987
fibo(17) =       1597
fibo(18) =       2584
fibo(19) =       4181
fibo(20) =       6765

解説

直接配列を返すのではなく、mallocでメモリを確保してから、ポインタを返す。