03章 函数.txt

C++大学教程txt版中文版 C++大学教程txt版中文版

    图3．14的程序用递归法计算并打印。到10的整数阶乘(稍后将介绍数据类型unsigned long的选择)。递归函数factorial首先测试终止条件是否为true，即number是否小于或等于1。如果number小于或等于1，则factorial返回1，不再继续递归，程序终止。如果number大于1，则下列语句。
    return number  *factorial( number - 1 )；
将问题表示为number乘以递归调用dactorial求值的number-1的阶乘。注意factorial(number-1)比原先factorial(number)的计算稍微简单一些。
1 // Fig. 3.14:fig03 14.cpp
2 // Recursive factorial function
3 #include <iostream.h>
4 #include <iomanip,h>
5
6 unsigned long factorial( unsigned long );
7
8 int main( )
9 {
10   for ( iht i = O; i <= 10: i++ )
11     cout << setw( 2)  << 1 << "! = "<< factorial( i ) << endl;
12
13   return 0;
14 }
15
16 // Recursive definition of function factorial
17 unsigned long factorial( unsigned long number )
18 {
19   if ( number <= 1 )  // base case
20     return 1;
21   else             // recursive case
22     return number * factorial( number - 1 );
23 }

输出结果：
    O! = 1
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! = 120
    6! = 720
    7! = 5040
    8! = 40320
    9! = 362880
    lO!= 3628800

                               图3．4用递归法计算阶乘

    函数factorial声明为接收unsigned long类型的参数和返回unsigned long类型的值。unsigned long是unsigned long int的缩写，C++语言的规则要求存放unsigned long int类型变量至少占用4个字节(32位)，因此可以取0到4294967291之间的值(数据类型long int至少占内存中的4个字节，可以取±2147483647之间的值)。如图3．14，阶乘值很快就变得很大。我们选择unsigned long数据类型，使程序可以在字长为16位的计算机上计算大于7!的阶乘。但是，factorial函数很快产生很大的值，即使unsigned long也只能打印少量阶乘值，然后就会超过unsigned long变量的长度。
    练习中将会介绍，用户最终可能要用float和double类型来计算大数的阶乘,这就指出了大多数编程语言的弱点，即不能方便地扩展成处理不同应用程序的特殊要求。从本书面向对象编程部分可以看到，C++是个可扩展语言，可以在需要时生成任意大的数。
    
    常见编程错误1．21
    递归函数中需要返回数值时不返回数值将使大多数编译器产生一个警告消息。
    常见编程错误3．22
    省略基本情况或将递归步骤错误地写成不能回推到基本情况会导致无穷递归，最终内存用尽。这就像迭代(非递归)解决方案中的无限循环问题。意外输入也可能导致无穷递归。

3.13  使用递归举例，Fibonacci数列
    Fibonacci数列(斐波纳契数列)：
    0，1，1，2，3，5，8，13, 21， ．．．
  以0和1开头．后续每个Fibonaeei数是前面两个Fibonacci数的和。
    自然界中就有这种数列,描述一种螺线形状。相邻Fibonacci数的比是一个常量1.618…,这个  数在自然界中经常出现，称为黄金分割(golden ratio或golden mean)。人们发现，黄金分割会产生最佳的欣赏效果。因此建筑师通常把窗户、房子和大楼的长和宽的比例设置为黄金分割数，明信片的长宽比也采用黄金分割数。

3.13  使用递归举例，Fibonacci数列
    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中每对输出行显示运行一次程序的结果。
1 // Fig. 3.15: fig03_lS.cpp
2 // Recursive fibonacci function
3 #include <iostream.h>
4
5 long fibonacci( long );
6
7 int main( )
8 {
9    long result, number;
10
11    cout << "Enter an integer: ";
12    cin >> number;
13    result = fibonacci( number );
14    tout << "Fibonacci{" << number << ") = "<< result << endl;
15    return 0;
16 }
17
18 // Recursive definition of function fibonacci
19 long fibonacci( long n )
2O {
21   if ( n == 0 || n == 1 )  // base case
22     return n;
23   else                 // recursive case
24     return fibonacei( n - 1 ) + fibonacci( n - 2 );
25 }

输出结果如下：
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

                          图 3．15递归计算Fibonacci数列

    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式的递归程序造成调用的指数性增加。

3．14  递归与迭代
    前面几节介绍了两个可以方便地用递归与迭代实现的函数。本节要比较递归与迭代方法，介绍为什么程序员在不同情况下选择不同方法。
    递归与迭代都是基于控制结构：迭代用重复结构，而递归用选择结构。递归与迭代都涉及重复：迭代显式使用重复结构，而递归通过重复函数调用实现重复。递归与迭代都涉及终止测试：迭代在循环条件失败时终止，递归在遇到基本情况时终止。使用计数器控制重复的迭代和递归都逐渐到达终止点：迭代一直修改计数器，直到计数器值使循环条件失败；递归不断产生最初问题的简化副本，直到达到基本情况。迭代和递归过程都可以无限进行：如果循环条件测试永远不变成false，则迭代发生无限循环；如果递归永远无法回推到基本情况，则发生无穷递归。
    递归有许多缺点，它重复调用机制，因此重复函数调用的开销很大，将占用很长的处理器时间和大量的内存空间。每次递归调用都要生成函数的另一个副本(实际上只是函数变量的另一个副本)．从而消耗大量内存空间。迭代通常发生在函数内，因此没有重复调用函数和多余内存赋值的开销。那么，为什么选择递归呢?
    
    软件工程视点3．14
    任何能用递归解决的问题也能用迭代(非递归)方法解决。递归方法优于迭代方法之处在于能更自然地反映问题，使程序更容易理解和调试。选择递归方法的另一个原因是可能没有明显的迭代方案。
    性能提示3．7
    在要求性能的情况下不要用递归方法。递归调用既花时间又占用更多的内存。
    常见编程错误3．24
    让非递归函数直接或通过另一函数间接调用自己是个逻辑错误。
    大多数有关编程的教材都把递归放在后面再讲。我们认为递归问题比较复杂而且内容丰富，应放在前面介绍，本书余下部分会通过更多例子加以说明。图3.17总结了本书使用递归算法的例子和练习。
    下面重新考虑书中重复强调的一些观点。良好的软件工程很重要，高性能也很重要，但是，这些目标常常是互相矛盾的。良好的软件工程是使开发的大型复杂的软件系统更容易管理的关键，面高性能是今后在硬件上增加计算需求时实现系统的关键，这两个方面如何取得折衷?
软件工程视点3．1 5
    让程序以整齐有序的层次方式工作能提高软件工程质量，但这是有代价的。
    性能提示1．8
    功能化的程序(而不是没有函数的一个整体的程序)造成更多的函数调用，需要占用执行时间和计算机处理器空间。但作为一个整体的程序难以编程、测试、调试、维护和改进。
    因此要使程序合理地功能化，应该一直保持性能与良好的软件工程之间的平衡。
    -----------------------------------------------------------------------
        章号                            使用递归算法的例子和练习
    -----------------------------------------------------------------------
        第3章

                                        阶乘函数
                                        Fbonacci函数
                                        最大公约数
                                        两个整数和
                                        两个整数积
                                        一个整数的整数次幂
                                        汉诺塔
                                        逆向打印键盘输入
        第4章
                                        图形化递归
                                        第4章
                                        数组元素求和
                                        打印数组
                                        逆向打印数组
                                        逆向打印字符串
                                        检查字符串是否为回文
                                        选择数组中的最小值
                                        选择排序
                                        八皇后
                                        线性查找
                                        折半查找
        第5章
                                        快速排序
                                        走迷宫
                                        逆向打印键盘输入字符串
        第15章
                                        链表插入
                                        链表删除
                                        链表搜索
                                        逆向打印链表
                                        二又树插入
                                        二又树前序遍历