Question

C语言用递推和递归两种算法完成斐波那契数列的计算，给一下代码

搞不懂递推和递归究竟有什么区别T T顺便解释一下吧~~

Answer 1

//递归法
int fibo1(int n)
{
if( n == 1 || n == 2) return 1;
else return fibo1(n-1)+fibo1(n-2);
}
//递推法
int fibo2(int n)
{
int f0=1,f1=1,f;
if (n<2)
return 1;
for(int i=2;i<n-1;i++)
{
f=f0+f1;
f0=f1;
f1=f;
}
return f;
}
区别：递推是直接使用已知的条件去推出未知的条件；递归则是将大问题逐渐转化为若干个相同的子问题，直到得到已知的最小子问题，再回溯依次得到父问题的答案。是由未知到已知，再从已知到未知。对于复杂的问题，递归把问题简单化，读起来易懂。

Answer 2

//递归，就是函数自己调用自己
#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));
}

Answer 3

#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;
}
此段程序将递归法和递推法计算斐波拉契函数的时间详细计算出，可以比较两个算法的时间复杂性。显然此处递推比递归算法要好得多。
递推就是从前往后推,递归还有个回溯的过程，通过调用自身函数完成计算。

Answer 4

引用447587096的回答：
//递归，就是函数自己调用自己
#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));
}

n==2呢？？