7.1递归函数1/例7-1：采用递归算法求n！#include<iostream>usingnamespacestd:1/函数fac（）：求阶乘的递归函数int fac(intn)if(n<0)11不能求负数的阶乘return -1;1/的阶乘为elseif(n==0)returnelsereturnn*fac(n-1）；1/nt为（n-1)乘以n
5 7.1 递归函数
7.1递归函数例7-1：采用递归算法求n！分析：用递归函数fac()计算5!时的执行过程如图7-1所示。fac(5)fac (4)fac(3)main(函数中调用调用调用调用fac (5)5*fac(4)4*fac(3)3*fac(2)返回6输出120返回120返回24fac (0)fac(1)fac(2)调用调用fac (0)=11*fac (0)2*fac(1)返回1返回1返回2图7-1递归函数的调用顺序
6 7.1 递归函数 例7-1：采用递归算法求n! 分析：用递归函数fac( )计算5!时的执行过程如图7-1所示。 图7-1 递归函数的调用顺序 调用 fac(5) 输出120 main()函数中 调用 5*fac(4) 返回120 fac(5) 调用 4*fac(3) 返回24 fac(4) 调用 3*fac(2) 返回6 fac(3) 调用 2*fac(1) 返回2 fac(2) 调用 1*fac(0) 返回1 fac(1) fac(0)=1 返回1 fac(0)
7.1递归函数注意：使用递归函数时，要特别注意不要造成死循环。一个问题要能够转换为递归来处理，必须满足以下条件：（1）必须包含一种或多种非递归的基本形式。(2）一般形式必须能最终转换到基本形式。(3)由基本形式来结束递归。注意：递归调用在堆栈中临时占据的存储区域是较多的，在实际运行时，递归调用的时间效率较差
7 7.1 递归函数 • 注意： 使用递归函数时，要特别注意不要造成死循环。 • 一个问题要能够转换为递归来处理，必须满足以下条件： • (1)必须包含一种或多种非递归的基本形式。 • (2)一般形式必须能最终转换到基本形式。 • (3)由基本形式来结束递归。 • 注意：递归调用在堆栈中临时占据的存储区域是较多的，在实 际运行时，递归调用的时间效率较差
7.1递归函数经典递归问题：Ackerman函数Fibonacci数列八皇后问题梵塔问题
8 7.1 递归函数 • 经典递归问题： • Ackerman函数 • Fibonacci数列 • 八皇后问题 • 梵塔问题
7.1递归函数例7-2：梵塔（hanoi塔）问题根据古印度神话，在贝拿勒斯的圣庙里安放着一个铜板，板上插有3根一尺长的宝石针。印度教的主神梵天在创造世界的时候，在其中的一根针上摆了由小到大共64片中间有孔的金片。无论白天和黑夜，都有一位僧侣负责移动这些金片，规则是一次只能将一片金片移到另一根针上，并且在任何时候以及任一根针上，小片永远在大片的上面。当所有的64片金片都由最初的那根针移到另一根针上时，这世界就将在一片霹雳中消失
9 7.1 递归函数 例7-2：梵塔(hanoi塔)问题 根据古印度神话，在贝拿勒斯的圣庙里安放着一个铜 板，板上插有3根一尺长的宝石针。印度教的主神梵天在 创造世界的时候，在其中的一根针上摆了由小到大共64 片中间有孔的金片。无论白天和黑夜，都有一位僧侣负 责移动这些金片，规则是一次只能将一片金片移到另一 根针上，并且在任何时候以及任一根针上，小片永远在 大片的上面。当所有的64片金片都由最初的那根针移到 另一根针上时，这世界就将在一片霹雳中消失