递归和非递归分别实现求第n个斐波那契数

青旅半醒 2022-05-26 11:36 157阅读 0赞

# 递归和非递归分别实现求第n个斐波那契数。 #

## 递归： ##

> 在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N\*）

#include<stdio.h>
    #include<stdlib.h>
    int fib(int n)
    {
        if(n<=2)
        {
            return 1;
        }
        else
        {
            return fib(n-1)+fib(n-2);
        }
    }
    int main()
    {
        int n = 0;
        int ret = 0;
        scanf("%d",&n);
        ret = fib(n);
        printf("%d",ret);
        system("pause");
        return 0;
    }

## 非递归 ##

> 一直以来很多C语言教科书在讲递归函数的时候总会拿斐波那契数列作为例子。但是这不意味着Fibonacci的最合适的解法就是用递归来实现。因为递归调用过程中有很多重复计算，而且重复的数量随着n的增加而剧增，实际上斐波那契递归时间复杂度是以n的指数级的方式递增,如果要计算第100个斐波那契数就要等很长时间了。

#include<stdio.h>
    #include<stdlib.h>
    int fib(int n)
    {
        int a = 1;
        int b = 1;
        int c = 0;
        while(n>2)
        {
            c = a+b;
            a = b;
            b = c;
            n--;
        }
        return b;
    }
    int main()
    {
        int n = 0;
        int ret = 0;
        scanf("%d",&n);
        ret = fib(n);
        printf("%d",ret);
        system("pause");
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关斐波那契数列（递归与非递归算法）

斐波那契数列，又称[黄金分割][Link 1]数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F

一时失言乱红尘/ 2022年09月19日 15:29/ 0 赞/ 280 阅读

相关 javascript 递归实现斐波那契数

斐波那契： 1 1 2 3 5 8 ..... 特点：后面的数等于前面两个数之和，即 f

我会带着你远行/ 2022年05月28日 05:28/ 0 赞/ 213 阅读

相关递归和非递归分别实现求第n个斐波那契数

递归和非递归分别实现求第n个斐波那契数。递归： > 在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-

青旅半醒/ 2022年05月26日 11:36/ 0 赞/ 158 阅读

相关斐波那契数列--递归与非递归实现

初识斐波那契数列：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖

ゝ一纸荒年。/ 2022年05月23日 05:40/ 0 赞/ 242 阅读

相关 python 递归实现斐波那契

斐波那契 def f(n): if n == 1 or n == 2: return 1

超、凢脫俗/ 2022年05月19日 11:14/ 0 赞/ 205 阅读

相关用递归和非递归实现斐波那契数列（C语言）

斐波那契数列（Fibonacci sequence），又称[黄金分割][Link 1]数列、因[数学家][Link 2]列昂纳多·斐波那契（Leonardoda Fibonac

素颜马尾好姑娘i/ 2022年05月09日 05:54/ 0 赞/ 250 阅读

相关斐波那契数列（递归及非递归）C/C++实现

递归实现斐波那契数列以下是正确C++源代码： 1.递归实现Fibonacci数列： include<iostream> inc

野性酷女/ 2022年04月03日 05:23/ 0 赞/ 329 阅读

相关斐波那契数列递归非递归实现

斐波那契数列是学习c语言递归时，必写的。递归实现代码 int fun(int n) //递归 { if(n==1||n==2)

桃扇骨/ 2022年03月30日 15:12/ 0 赞/ 248 阅读

相关递归求斐波那契数列

斐波那契数列题目描述：编写一个函数，求斐波那契数列的第n项的值。首先，对于斐波那契数列，我们是非常熟悉了，对斐波那契定义为如下：f(0)=0,f(1)=0,f(2)=1

左手的ㄟ右手/ 2021年11月17日 12:34/ 0 赞/ 400 阅读

相关斐波那契_尾递归

(1)计算任意数n的阶乘 5! 54321 8! 87654321 ''' 递归函数通过两个条件出发回的过程: (1) 当

悠悠/ 2021年11月13日 18:50/ 0 赞/ 329 阅读