专栏首页海天一树小朋友学C语言(17):斐波那契数列的递归实现

小朋友学C语言(17):斐波那契数列的递归实现

什么是递归呢?先举个例子:

从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?"从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?'从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?……'"

这个例子里,故事内嵌套着故事,构成了递归。

动手编写程序:

#include <stdio.h>
int fibonacci(int n) 
{
    if(1 == n || 2 == n)
    {
        return 1;
    }
    return fibonacci(n-2) + fibonacci(n - 1);
}
int main() 
{
    int m;
    printf("input m: ");
    scanf("%d", &m);
    int result = fibonacci(m);
    printf("fibonacci(%d) = %d\n", m, result);
    return 0;   
}

运行结果:

input m: 5
fibonacci(5) = 8

新知识点: (1) 函数调用自身,就叫函数的递归调用。这个程序里,fibonacci()函数就调用了它本身。 但是不要以为return语句有两个fibonacci()函数,就误认为是2次调用自身。实际的调用次数是不固定的,要看n的值 。 咱们这里以n=5为例。 按照程序,有 fiboccina(5) = fiboccina(5 - 2) + fiboccina(5 - 1) = fiboccina(3) + fiboccina(4) ① fiboccina(3)和fiboccina(4)同样会调用fiboccina()函数自身: fiboccina(3) = fiboccina(3 - 2) + fiboccina(3 - 1) = fiboccina(1) + fiboccina(2) ② fiboccina(4) = fiboccina(4 - 2) + fiboccina(4 - 1) = fiboccina(2) + fiboccina(3) ③

在②式里,fiboccina(1)和fiboccina(2)都不会调用自身, 因为n=1或n=2的时候,直接返回1。 所以fiboccina(3) = 1 + 1 = 2

在③中,fiboccina(2) = 1,fiboccina(3)会调用自身。 fiboccina(3) = fiboccina(1) + fiboccina(2) = 1 + 1 = 2 所以,fiboccina(4) = fiboccina(2) + fiboccina(3) = 1 + 2 = 3

将求得的fiboccina(3)和fiboccina(4)的值代入①,得 fiboccina(5) = fiboccina(3) + fiboccina(4) = 2 + 3 = 5,即为最终结果。

(2) 从(1)中的分析过程,可以看出n=5的时候,程序的执行顺序为 ①-->②-->③-->④-->⑤-->⑥-->⑦-->⑧-->⑨

(3) 从(1)和(2)的分析过程可以看出,n为1或2是递归的终止条件。无论原先输入的正自然数n的值是多少,最终都会递归减少到n=1或n=2的情况。

开头讲的那个例子,不是严格的递归,因为那个故事是讲不完的,没有终止条件。

作业: (1)执行断点前,在fibonacci()加上printf(“n = %d\n”, n);

int fibonacci(int n) 
{
        printf(“n = %d\n”, n);
    if(1 == n || 2 == n)
    {
        return 1;
    }
    return fibonacci(n-2) + fibonacci(n - 1);
}

输入n = 1,用断点查看程序的执行过程。 输入n = 2,用断点查看程序的执行过程。 输入n = 3,用断点查看程序的执行过程。 输入n = 4,用断点查看程序的执行过程。 输入n = 5,用断点查看程序的执行过程。 输入n = 6,用断点查看程序的执行过程。

(2)默写这个程序

本文分享自微信公众号 - 海天一树(gh_de7b45c40e8b),作者:海天一树

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-11-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 人工智能、数据挖掘、机器学习和深度学习的关系

    一、人工智能 人工智能(Artificial Intelligence),英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统...

    海天一树
  • 某公司自然语言处理算法笔试题

    1 请列出几种文本特征提取算法 答:文档频率、信息增益、互信息、X^2统计、TF-IDF 2 简述几种自然语言处理开源工具包 答:LingPipe、FudanN...

    海天一树
  • 小朋友学Python(14):日期和时间

    一、获取当前时间戳 例1 import time now = time.time() print now 运行结果: 1512884891.53 说明: 这里得...

    海天一树
  • 利用腾讯云 COS 云对象存储定时远程备份网站

    一、优点分析 内网传输:和阿里云 OSS 一样,腾讯云 COS 同样支持内网和外网文件传输,对于腾讯云服务器,使用内网传输绝对是最快、最稳定的备份方案! 免费...

    张戈
  • django:自定义静态文件服务器

    静态文件使用nginx是比较有效率的,但是有时,我们需要对文件下载做细粒度的处理,比如鉴权下载,此时就需要写代码了。 下面将一步步实现一个自定义的文件handl...

    超级大猪
  • Android—Room 数据库迁移(Migration)

    code_horse
  • 剑指offer - 调整数组顺序使奇数位于偶数前面 - JavaScript

    path.sep,是路径片段分隔符。它在 Windows 上是\,在 Unix 上是/。它用于指定文件(夹)的路径中。

    心谭博客
  • NodeJS模块研究 - path

    path.sep,是路径片段分隔符。它在 Windows 上是\,在 Unix 上是/。它用于指定文件(夹)的路径中。

    心谭博客
  • Python读取PDF文档并翻译

    翻译服务选择免费的百度翻译api:https://api.fanyi.baidu.com/

    小锋学长
  • NodeJs-path模块

    今天是除夕节日,明天就是春节了。这个春节大家都不要出去乱跑了,在家呆着是最安全的。为奋战在一线的医护工作者加油,他们同样是父母,同样是子女,真的非常不容易。大家...

    efonfighting

扫码关注云+社区

领取腾讯云代金券