斐波那契数列的定义为：她的第1项和第2项均为1，以后各项为其前2项之和，若斐波那契数列中的第N项用Fib(n)表示，则计算公式为：
Fib(n)={1 (n=1或者2）
{Fib(n-1)+Fib(n-2) (n>2)
试写出计算 Fib(n)的递归算法和递归算法，并分析它们的时间复杂度和空间复杂度。

#include<stdio.h>
#define N 15
void fun1();//非递归非数组
void fun2();//非递归数组
int fun3(int);//递归
void main(){
fun1();
putchar(10);
fun2();
putchar(10);
for(int i=1;i<=N;i++)
printf(\"%d \",fun3(i));
}

void fun1()
{
 int x=1,y=1,count=1;
 printf(\"%d \",x);
 while(count<N)
 {printf(\"%d \",y);
 y=x+y;
 x=y-x;
 count++;}
}
void fun2()
{
 int a[20]={1,1};
 for(int i=2;i<N;i++)
  a[i]=a[i-1]+a[i-2];
 for(int j=0;j<N;j++)
  printf(\"%d \",a[j]);
}
int fun3(int n)
{if(n==1||n==2) return 1; 
else return fun3(n-1)+fun3(n-2);
}

也可以用叠代

非常感谢帮助我的人！