小朋友学C语言（17）：斐波那契数列的递归实现

素颜马尾好姑娘i 2022-06-07 12:52 94阅读 0赞

什么是递归呢？先举个例子：

> 从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？”从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？’从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

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

动手编写程序：

#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的时候，程序的执行顺序为  
①–>②–>③–>④–>⑤–>⑥–>⑦–>⑧–>⑨

![fiboccina.png][]

（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）默写这个程序

> 更多内容请关注微信公众号  
> ![wchat\_official.jpg][wchat_official.jpg]

[fiboccina.png]: /images/20220607/0d91024da80a4adfa84a2499ee67de17.png
[wchat_official.jpg]: /images/20220607/e5db80eb16084d73aa2dd457099b3b9d.png