用递归和非递归的方法输出斐波那契数列的第n个元素（C语言实现）

简介

费波那契数列（意大利语：Successione di Fibonacci），又译为费波拿契数、斐波那契数列、费氏数列、黄金分割数列。

公式

在数学上，费波那契数列是以递归的方法来定义： (分段函数)

n ≧ 2 时: $F_{n}=F_{{n-1}}+F_{{n-2}}$
n = 1 时: $F_{1}=1$
n = 0 时: $F_{0}=0$

注意:

1. 递归边界为n=1;
2. 实际上n=0时的情况是不存在的，只是为了方便计算，这里设置为了0;

用文字来说，就是费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出。
首几个费波那契系数是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ...

特别指出：0不是第一项，而是第零项。

C语言实现

#include <stdio.h>

int fib1 (int n) ;    //非递归生成下标为n的斐波那契数列元素
int fib2 (int n) ;    //递归生成下标为n的斐波那契数列元素

int main ()
{
    int n ;

    printf("please input the index of fib:") ;
    scanf("%d" , &n) ;
    printf("the %d fib1 number is %d 
" , n , fib1(n)) ;
    printf("the %d fib2 number is %d 
" , n , fib2(n)) ;

    return 0 ;
}

int fib1 (int n)
{
    int i = 0 ;
    int a = 1 ;
    int b = 1 ;
    int result = 0 ;

    if(n <= 0)
    {
        return 0 ;
    }
    else if(n <= 2)
    {
        return 1 ;
    }
    else
    {
        for(i = 3 ; i <= n ; i ++)
        {
            result = a + b ;
            a = b ;
            b = result ;
        }
        return result ;
    }
}

int fib2(int n)
{
    if(n <= 0)
    {
        return 0 ;
    }
    else if(n <= 2)
    {
        return 1 ;    //递归终止条件
    }
    else
    {
        return fib2(n-1) + fib2(n-2) ;    //递归
    }
}

来源: https://www.cnblogs.com/maoguy/p/6629478.html