Fibonacci数列の再起関数について

質問

Ｆｎ＝Ｆn-1＋Ｆn-2 (N以上２）
F0=F1=1
Ｆ0～Ｆ10までの値を表示する。
のときの再帰的関数を用いる方法と用いない方法をおしえていただけませんか？
すごく悩んでて困っています。

回答No.1

noname#16581 · ベストアンサー

多分、以下のようにするといいと思います。
#include<stdio.h>
/* Not Fibonacci
int Fibonacci(int a,int b)
{
return a+b;
}
int main()
{
int Num[10];
Num[0]=1;
Num[1]=1;
for(int i=2;i<10;i++)
{
Num[i]=Fibonacci(Num[i-1],Num[i-2]);
}
for(int i=0;i<10;i++)
{
printf("%d ",Num[i]);
}
getchar();
return 0;
}
*/
// Use Fibonacci
int Fibonacci(int MaxCnt,int Cnt,int a,int b)
{
if(MaxCnt==0 ||MaxCnt==1){return 1;}
if(Cnt==MaxCnt){return a;}
return Fibonacci(MaxCnt,Cnt+1,b,a+b);
}
int main()
{
int Cnt=0;
int Num[10];
for(int i=0;i<10;i++)
{
Num[i]=Fibonacci(i,0,1,1);
}
for(int i=0;i<10;i++)
{
printf("%d ",Num[i]);
}
getchar();
return 0;
}

お礼

ありがとうございます。すごくためになりました。
　もう１つよろしかったらお願いを聞いていただけませんか？
　今回の回答に対して解析または考察についてもおしえていただけませんか？
　よろしくお願いします。

補足

今回のアルゴリズムすごくためになりました。ありがとうございました。このアルゴリズムに対して考察または解析するとすればどうのようなことが考えられるか教えて頂けませんか？

回答No.2

xcrOSgS2wY

再帰関数を使用する場合のほうは、Fibonacci数列の定義をそのまま関数にするだけです。例えばこんな感じ。（どこに悩む余地があるのか、ちょっと悩みますが。）

fib(n)
{
　　if (n >= 2) return fib(n-1) + fib(n-2);
　　return 1;
}

非再帰関数を使用する場合は、2つの方法が考えられます。

1つはF(0)からF(n)まで1つずつ順番に求める方法です。
例えばこんな感じ。

　　fib[0] = 1;
　　fib[1] = 1;
　　fib[2] = fib[0] + fib[1];
　　fib[3] = fib[1] + fib[2];
　　...

よく考えれば、これをループにすることもたやすいはずです。

もう1つはF(n) = F(n-1) + F(n-2)という漸化式をnに関する関数に解いてしまう方法です。例えば、関数式がF(n) = 2^n / 5だとすれば

　　fib[n] = pow(2, n) / 5;

のような式になります。

注：この式は間違っています。こんなふうにFibonacci数列はnについて解くことができるという意味です。正しい式は自力で解いて求めてください。