c语言斐波那契数列12,小朋友学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

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

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的时候，程序的执行顺序为

①–>②–>③–>④–>⑤–>⑥–>⑦–>⑧–>⑨

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