函数II 递归.ppt

《函数II 递归.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、函数II递归变量的作用域定义在函数内或块内的变量称为局部变量（localvariable）。在函数外部定义的变量称为全局变量(globalvariable)。1.递归的定义什么是递归？说白了就象我们熟悉的那个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。即递归就是一个对象在定义时用到了自身。这个对象可以是函数、概念、数学结构…因为故事中包含了故事本身，如果用程序实现，必然是一个对象（函数）直接或间接地调用了其自身。voidStory(){cout<<“从

2、前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：”;cin.get();//按任意键听下一个故事Story();//老和尚讲的故事，实际上就是上面那个故事}voidStory(intn){if(n

3、口。（注：要确保边界条件能够被执行到）递归的使用场合数据的定义形式按递归定义问题的求解通过子问题来解决例：求n的阶乘n!（n！=1*2*…*n）分析：我们可以这样定义n!，n!=n(n-1)!，因此求n!转化为求(n-1)!。这就是一个递归的描述。因此，可以编写如下递归程序：intfac(intn){if(n==0)return1;//边界条件returnn*fac(n-1);//else也可}下图展示了N=3的执行过程递归调用示例图由此可知，递归的执行过程分递推和回归两个阶段在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于

4、n）的求解。例如求n!转化为求(n-1)!,依次类推，直至计算到n=0时。在递推阶段，必须要有终止递归的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。例如知道0！=1，可以得到1！=1，2！=2，…，直到n！任务：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法。【例】汉诺塔问题。有A、B、C三根柱子，A柱上有n个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由A柱搬动到C柱上，每次只能搬动一个盘子，搬动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。打印出搬动的步骤。A柱B

5、柱C柱分析：1A柱只有一个盘子的情况：A柱C柱；2A柱有两个盘子的情况：小盘A柱B柱，大盘A柱C柱，小盘B柱C柱。3A柱有n个盘子的情况：将此问题看成上面n-1个盘子和最下面第n个盘子的情况。n-1个盘子A柱B柱，第n个盘子A柱C柱，n-1个盘子B柱C柱。问题转化成搬动n-1个盘子的问题，同样，将n-1个盘子看成上面n-2个盘子和下面第n-1个盘子的情况，进一步转化为搬动n-2个盘子的问题，……，类推下去，一直到最后成为搬动一个盘子的问题。这是一个典型的递归问题，递归结束于只搬动一个盘子。函数的递归调用算法可以描述为：1n-1个盘子A柱B柱

6、，借助于C柱；2第n个盘子A柱C柱；3n-1个盘子B柱C柱，借助于A柱；其中步骤1和步骤3继续递归下去，直至搬动一个盘子为止。由此，可以定义两个函数，一个是递归函数，命名为hanoi(intn,charsource,chartemp,chartarget)，实现将n个盘子从源柱source借助中间柱temp搬到目标柱target；另一个命名为move(charsource,chartarget)，用来输出搬动一个盘子的提示信息。程序如下：#includevoidmove(charsource,chartarget){cout<<

7、source<<"->"<>n;hanoi

8、(n,'A','B','C');}任务：用辗转相除法求最大公约数任