编写一个函数，求第n个斐波那契数。【递归 + 非递归】

​

​编写一个函数，求第n个斐波那契数。【递归 + 非递归】​

​

//非递归
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string>
int fibo(int n)
{
  int i = 0;
  int f1 = 1, f2 = 1, f3= 0;
  for (i = 0; i < n - 2; i++)
  {
    f3 = f1 + f2;                   //第三个数等于前两个数之和
    f1 = f2;                        
    f2 = f3;
  }
  return f3;
}
int main()
{
  int a = 0;
  scanf("%d", &a);
  printf("%d\n", fibo(a));
  system("pause");
  return 0;
}      

递归分析如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string>
//递归
int fibo(int n)
{
  if (n < 3)
  {
    return 1;
  }
  else
  {
    return (fibo(n - 1) + fibo(n - 2));
  }
}
int main()
{
  int a = 0;
  scanf("%d", &a);
  //fibo(a);
  printf("%d", fibo(a));
  system("pause");
  return 0;
}      

运行结果如下：