小朋友学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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏枕边书

设计模式,Let's “Go”! (上)

前言 最近读了《Head First 设计模式》,每天早上看一章,学习一个设计模式,做些笔记,然后晚上抽空用刚学习的 Go 语言实现一下。半个月下来书读完了,留...

20050
来自专栏静晴轩

IOS 8 Safari JIT bug影响jQuery和underscore

前端时间为移动游戏做一个网页活动需求(9宫格的刮奖),遇到一个很诡异的问题:Android端OK,就是在Ios设备上,点击非第一块区域,显示却是第一块区域被刮开...

36560
来自专栏北京马哥教育

shell十三问,为linux学习打基础(二)

本文整理并转自CU上的帖子[学习共享] shell 十三問?,此贴是2003年发表的,但却是相当不错的linux基础知识汇集贴,原帖主使用的台湾风格,本文加以简...

40440
来自专栏狮乐园

简单探索 js 中 something >> 0 的原理

关于这个问题是今天改公司项目小程序的一个bug时看到的,修复这个bug的解决方法是需要引入 String.prototype.padStart 的 polyfi...

12530
来自专栏灯塔大数据

每周学点大数据 | No.67 Hadoop 实践案例——记录去重

No.67 Hadoop 实践案例——记录去重 Mr. 王:现在我们看一个和 WordCount 很相似,在实际中应用也很多的例子——记录去重。 小可 :嗯,...

34380
来自专栏Python入门

你还在为Python中文乱码而感到烦恼?今天老司机给你讲讲!

有没有遇到过这样的问题,读取文件被提示“UnicodeDecodeError”、爬取网页得到一堆乱码,其实这些都是编码惹的祸,如果不能真正理解编码的问题所在,就...

19930
来自专栏大内老A

WCF技术剖析之二十二: 深入剖析WCF底层异常处理框架实现原理[上篇]

对于上一篇文章 (WCF基本异常处理模式:[上篇]、[中篇]、[下篇]),主要是站在最终开发者的角度对WCF关于异常处理编程模式进行了介绍,接下来,我们需要将我...

21090
来自专栏极客猴

基础知识 | 使用 Python 将数据写到 CSV 文件

我们从网上爬取数据,最后一步会考虑如何存储数据。如果数据量不大,往往不会选择存储到数据库,而是选择存储到文件中,例如文本文件、CSV 文件、xls 文件等。因为...

11420
来自专栏安恒网络空间安全讲武堂

赛前福利②最新2018HITB国际赛writeup

FIRST 距离“西湖论剑杯”全国大学生网络空间安全技能大赛只有9天啦! 要拿大奖、赢offer,那必须得来点赛前练习定定心啊~这不,讲武堂就拿到了2018HI...

34740
来自专栏Golang语言社区

【翻译】为什么 goroutine 的栈内存无穷大?

一些 Go 语言的新学习者总是会对 goroutine 栈内存占用大小感到非常好奇。这一般是由于程序员进行无限的函数循环调用导致的。为了说明这个问题,请思考以下...

37260

扫码关注云+社区

领取腾讯云代金券