递归--斐波那契数列

#include <stdio.h>
//斐波那契数列的非递归实现
int f(int n)
{
    int a,b,sum;
    sum=0;
    a=1;b=1;
    if (n==1||n==2)
        return 1;
    for (int i = 2; i < n; ++i) {
        sum=a+b;
        a=b;
        b=sum;
    }
    return sum;
}
//斐波那契数列的递归求解
/*
 * 斐波那契数列解决办法
 *  1.先罗列一些序列,看是不是有规律,
 *  2.如果能把一个大问题分解为一个小问题,则使用递归
 *
 * 递归问题:
 *  1.递归函数定义形式  int f_f(int n)
 *  2.递归条件    if(n>2){递归},if(n==1||n==2) return 1;
 *  3.递推表达式   f(n)=f(n-1)+f(n-2)
 */
int f_f(int n)
{
    if (n==1||n==2)
    {
        return 1;
    }
    return f_f(n-1)+f_f(n-2);
    //把f(n-1)+f(n-2)传入int f_f(int n),就构成了递推表达式,f_f(n)=f_f(n-1)+f_f(n-2)
}
int main()
{
    int n;  //项数

    scanf("%d",&n);
    
    int i=f(n);
    printf("第n项为:%d\n",i);
    
    i=f_f(n);
    printf("第n项为:%d\n",i);
    return 0;
}