3.13 使用递归举例，Fibonacci 数列

优质

小牛编辑

133浏览

2023-12-01

Fibonacci 数列(斐波纳契数列)：

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

以0和1开头．后续每个 Fibonaeei 数是前面两个 Fibonacci 数的和。

自然界中就有这种数列,描述一种螺线形状。相邻Fibonacci数的比是一个常量1.618…,这个数在自然界中经常出现，称为黄金分割(golden ratio或golden mean)。人们发现，黄金分割会产生最佳的欣赏效果。因此建筑师通常把窗户、房子和大楼的长和宽的比例设置为黄金分割数，明信片的长宽比也采用黄金分割数。

Fibonacci 数列可以递归定义如下：

fibonacci(O)=O
fibonacci(1)=l
fibonacci(n)= fibonacci{n-1)+ fibonacci(n-2)

图3.15的程序用函数fibonaoci递归计算第i个Fibonacci数。

注意Fibonacci数很快也会变得很大，因此把Fibonacci函数的参数和返回值类型设为unsigned long数据类型。

图3.11中每对输出行显示运行一次程序的结果。

// Fig. 3.15: fig03_lS.cpp
// Recursive fibonacci function
#include 

long fibonacci( long );

int main(){
  long result, number;

  cout << "Enter an integer: "; cin >> number;
  result = fibonacci( number );
  tout << "Fibonacci{" << number << ") = "<< result << endl;
    return 0;
  }

  // Recursive definition of function fibonacci
  long fibonacci( long n ){
    if ( n == 0 || n == 1 )  // base case
    return n;
    else  // recursive case
    return fibonacei( n - 1 ) + fibonacci( n - 2 );
  }
}

输出结果如下：

Enter an integer: 0
Fibonacci(0) = 0
Enter an integer: 1
Fibonacci(1) = 1
Enter an integer: 2
Flbonacci(2) - 1
Enter an integer: 3
Fibonacci(3) - 2
Enter an integer: 4
Fibonacci(4) = 3
Enter an integer: 5
Fibonacci(5) = 5
Enter an integer: 6
Fibonacci(6) = 8
Enter an integer: 10
Fibonacci(10) = 55
Enter an integer: 20
Fibonacci(20) = 6765
Enter an integer: 30
Fibonacci(30) = 832040
Enter an integer: 35
Fibonacci(35) = 9227465

main中调用fibonacci函数不是递归调用，但后续所有调用fibonacci函数都是递归调用。每次调用fibonacci时．它立即测试基本情况(n等于0或1)。如果是基本情况，则返回n。有趣的是，如果n大于1，则递归步骤产生两个递归调用，各解决原先调用fibonacci问题的一个简化问题。图9．16显示了fibonacci函数如何求值fibonacci(3)，我们将fibonacci缩写成f。

图中提出了C++编译器对运算符操作数求值时的一些有趣的顺序问题。这个问题与运算符作用于操作数的顺序不同，后者的顺序是由运算符优先级规则确定的。图3．16中显示，求值f(3)时，进行两个递归调用，即f(2)和f(1)。但这些调用的顺序如何呢?

大多数程序员认为操作数从左向右求值。奇怪的是，C++语言没有指定大多数运算符的操作数求值顺序(包括+)，因此，程序员不能假设这些调用的顺序。调用可能先执行f(2)再执行f(1)，也可能先执行f(1)再执行f(2)在该程序和大多数其他程序中，最终结果都是相同的。但在有些程序中，操作数求值顺序的副作用可能影响表达式的最终结果。

C++语言只指定四种运算符的操作数求值顺序，即"&&"、"||"、逗号运算符(，)和“?：”。前三种是二元运算符，操作数从左向右求值。第四种是C++惟一的三元运算符，先求值最左边的操作数，如果最左边的操作数为非0，则求值中间的操作数，忽略最后的操作数；如果最左边的操作数为0，则求值最后的操作数，忽略中间的操作数。

常见编程错误3.23

对于除“&&”、"||"、逗号运算符(,)和"?："以外的运算符，如果在编写程序中依赖该运算符择作数的求值顺序，则会导致错误，因为编译器不一定按程序员希望的顺序求值操作数。

可移植性提示3 2

对于除”&&”、"||"、逗号运算符(,)和"?："以外的运算符，如果在程序中依赖该运算符操作数的求值顺序，则不同系统和不同编译器中的结果不同。

要注意这类程序中产生Fibonacci数的顺序。Fibonacci函数中的每一层递归对调用数有加倍的效果，即第n个Fibonaeci数在第2n次递归调用中计算。计算第20个Fibonacci数就要220次，即上百万次调用，而计算第30个Fibonacci数就要230次，即几十亿次调用。计算机科学家称这种现象为指数复杂性(exponential complexity)，这种问题能让最强大的计算机望而生畏。一般复杂性问题和指数复杂性将在高级计算机科学课程“算法”中详细介绍。

性能提示1.6

避免fibonacci式的递归程序造成调用的指数性增加。