第1个回答 推荐于2017-09-11
//递归,就是函数自己调用自己
#include <stdio.h>
int feibonaqie(int n)
{
if(n == 0 )
return 0;
if(n == 1)
return 1;
else
return feibonaqie(n-1) + feibonaqie(n-2);
}
int main(void)
{
int n = 20 ;//假设输出20个数吧
int i;
for(i = 0; i <= n; i++)
printf("%d ",feibonaqie(i));
}本回答被提问者采纳
第2个回答 2018-03-21
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void main()
{
clock_t start, finish;
double duration=0;
int n;
printf ("input the data n=:");
scanf ("%d",&n);
start = clock();
fib(n);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "递归法用时=%f seconds\n", duration );
start = clock();
fic(n);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "递推法用时=%f seconds\n", duration );
}
//递归法
int fib(int n)
{
if( n == 1 || n == 2) return 1;
else return fib(n-1)+fib(n-2);
}
//递推法
int fic (int n)
{
int f0=1,f1=1,f2,i=2;
if (n<2)
return(n);
while (i<=n)
{
f2=f1+f0;
f0=f1,f1=f2;
i++;
}
return f2;
}
此段程序将递归法和递推法计算斐波拉契函数的时间详细计算出,可以比较两个算法的时间复杂性。显然此处递推比递归算法要好得多。
递推就是从前往后推,递归还有个回溯的过程,通过调用自身函数完成计算。