フィボナッチ数列 プログラミング C言語

質問

「フィボナッチ数を次の手順で求めるプログラムfib2.cを作成。
再帰関数 int fib(int n)を定義し，再帰呼出しによりfib(n)の値を求める。ｎ＝３０までのフィボナッチ数を求めて表示せよ。
またどのnの値まで求めるか？」という問題です。

で下記のように作りましたが再帰関数をつかわなかったので再提出になってしまいました。
再帰関数はどうやって使うのでしょうか。
今回の場合はどの部分が再帰関数になるのでしょうか？
おねがいします。

#include<stdio.h>

main()
{
int fib[100], i;

fib[0] = 0;
fib[1] = 1;
printf("F0=0\nF1=1\n");

for(i=2; i<=30; i++)
{
fib[i] = fib[i-1]+fib[i-2];
printf("F%d=%d\n",i, fib[i]);
}
}

回答No.3

minaraiH · ベストアンサー

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

long fib_a(int n); //再帰版
long fib_b(int n); //非再帰版

int main(){
int n;
printf("0以上45以下の整数を入力せよ");
scanf("%d",&n);
assert(0<=n && n<=45);
printf("フィボナッチ数列の第%d項:%ld,%ld\n",n,fib_a(n),fib_b(n));
return EXIT_SUCCESS;
}

long fib_a(int n)
{
return n < 2 ? 1 : fib_a(n-1)+fib_a(n-2);
}

long fib_b(int n)
{
long e,f,w;
int i;

e=0; f=1;
for(i=0;i<n;i++){
w=f; f+=e; e=w;
}
return f;
}

補足

どうして４５以下でないといけないのですか？

回答No.4

minaraiH

longとfibの間は空白あけてください。同一文字みたいになった・・

回答No.2

Yanch

大まかなプログラムの構造は以下の様な感じであると思います。
----------------------------------------------------------------------
#include<stdio.h>

int fib(int n);

int main(int argc, char *argv[])
{
　　int n;

　　for(n = 0; n <= 30; n++)
　　{
　　　　printf("fib(%d)=%d\n",n, fib(n));
　　}
}

int fib(int n)
{
　　/*
　　 * TODO:フィボナッチ数を求める処理をここに記述
　　 */

　　return 0;
}
----------------------------------------------------------------------
再起関数ですが、
fib()関数内より、fib()関数を呼び出すような処理を記述してあげるとよいでしょう。
「fib(n - 1);」等です。

回答No.1

eroermine

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

fib()の中でfib()を呼ぶようなのが再帰。
これは自分の中で自分を二回呼んでるので難易度高?
一時変数の無いことに注目してください。