Osheep

时光不回头,当下最重要。

小朋友学C语言(12):斐波那契数列和递归

一、斐波那契简介

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368……..
这个数列从第3项开始,每一项都等于前两项之和。

二、非递归实现

动手编写程序:

#include <stdio.h>

int fibonacci(int n) 
{
    if(1 == n || 2 == n)
    {
        return 1;
    }
    
    int f1 = 1;
    int f2 = 1;
    int i, f3;
    
    for(i = 3; i <= n; i++)
    {
        f3 = f1 + f2;
        f1 = f2; 
        f2 = f3;
    }
    
    return f3;
}

int main()
{   
    int n, result;
    
    printf("input n: ");
    scanf("%d", &n);
    
    result = fibonacci(n);
    
    printf("The result is %d", result);
   
    return 0;
}

运行结果:

input n: 6
The result is 8

新知识点:
(1)这里出现了一个新的函数scanf()。scanf()的作用是读取键盘或鼠标的输入。n是你通过键盘输入的值,&是取地址符,&n就是n在内存里的地址。找到了n在内存中的地址,也就取到了n的值。
假如你输入n 的值为 3,则&n就是3在内存里的地址,则n就是3。
scanf()的作用与printf()的作用相反。printf()的作用是打印、输出。
这两个函数都是在stdio.h中声明的。
【注意】多数线上编译器不支持scanf()函数,所以这个程序要用本机编译器(比如苹果电脑的Xcode,PC的dev c++)来编译。

(2)
if(1 == n || 2 == n)
{
return 1;
}
这段表示,假如你输入的n为1或2,则返回1。下面的语句都不被执行。

(3) 1 == n
像这种比较句式,写成1 == n或n == 1,结果是一样的,都是比较n和1是否相等。
但是推荐1 == n的写法。为什么呢?因为有时候写代码的时候,由于粗心会少打一个等号,变成了1 = n或n = 1。这个时候差别就大了。
如果是 n = 1的话 ,这是赋值语句,if(n = 1)相当于if(1),这个条件永远为真(因为1为真,0为假)。
如果是1 = n的话,变量是不能赋值给常量的,编译器会在这一行报语法错误,你看到之后,立马会发现这行有错,从而把漏写的等号补上去。

(4)看下面的两行代码
int i = 0;
if( i == 0)
这里i == 0为真,if(i == 0)相当于if(1),恒为真

如果if语句里少写了一个等号,误写成
int i = 0;
if(i = 0)
这里第一句是把0赋值给i,第二句if里,再次把0赋值给a,if(i = 0)相当于if(0),恒为假。这样因为少写了一个等号,就得到了与事实相反的结果。

再强调一下,判断语句要写成if(常量 == 变量)不要写成if(变量 == 常量),就是为了怕少写一个等号引起错误。

(5)假如你输入的值大于2,比如你输入了6,则fibonacci()函数中的for循环是这么执行的:
第一次,i = 3, i <= 6为真,f3 = f1 + f2 = 1 + 1 = 2, f1 = f2 = 1, f2 = f3 = 2
第二次,i = 4, i <= 6为真,f3 = f1 + f2 = 1 + 2 = 3, f1 = f2 = 2, f2 = f3 = 3
第三次,i = 5, i <= 6为真,f3 = f1 + f2 = 2 + 3 = 5, f1 = f2 = 3, f2 = f3 = 5
第四次,i = 6, i <= 6为真,f3 = f1 + f2 = 3 + 5 = 8, f1 = f2 = 5, f2 = f3 = 8
第五次,i = 7, i <= 7为假,循环结束。最终返回的f3的值为8

作业:
(1)输入n = 6,用断点查看程序的执行过程。
(2)输入n=1或n=2,用断点查看程序的执行过程。
(3)在纸上默写这个程序

三、递归实现

动手编写程序:

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

《小朋友学C语言(12):斐波那契数列和递归》

fiboccina.png

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

作业:
(1)断点查看运行步骤,可在fibonacci()加上printf(“n = %d\n”, n);来查看每次进入fibonacci()函数时n的取值:

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

(2)默写这个程序

点赞