文档介绍：第11章 递推与递归开始*主要内容递推递归递归与分治递归与回溯*递归的概念先看大家都熟悉的一个民间故事:从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说,从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说……。象这样,一个对象部分地由它自己组成,或者是按它自己定义,我们称之为递归。递归的定义: 在一个函数的定义中又直接或间接地调用该函数本身,称为递归。递归是一种非常有用的程序设计方法。*递归算法的基本思想把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题,并且小到一定程度可以直接得出它的解,从而得到原来问题的解。递归算法的特点用递归算法编写的程序结构清晰,具有很好的可读性;但程序的效率比较低。*递归的应用场合当问题具备以下特点之一时,往往采用递归算法来解决:问题本身是递归定义的,i数列问题;问题涉及到的数据结构是递归定义的,如树、图等;问题的解决方法是递归形式的,如汉诺塔问题;*例输出Fibonacii数列的第n项#include<>intfib(intn){ if(n<=1)return1; elsereturnfib(n-1)+fib(n-2);}voidmain(){ intn; scanf("%d",&n); printf("%d\n",fib(n));}*上面是斐波那契数列的递归调用树,可以看出同一个fib(i)被调用多次,因此递归算法编写的程序效率比较低。Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)*递归设计的要件(1)在函数中必须有直接或间接调用自身的语句;(2)在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口(或递归边界)。*编写递归算法时,首先要对问题的以下三个方面进行分析:决定问题规模的参数。需要用递归算法解决的问题,其规模通常都是比较大的,在问题中决定规模大小(或问题复杂程度)的量有哪些?把它们找出来。问题的边界条件及边界值。在什么情况下可以直接得出问题的解?这就是问题的边界条件及边界值。解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题,需要通过哪些步骤或等式来实现?这是解决递归问题的难点。把这些步骤或等式确定下来。*(Hanoi)塔问题(1)相传在古代印度的一个寺庙中,有位僧人整天把三根柱子上的金盘倒来倒去,原来他是想把64只一个比一个小的盘子从柱子A上借助柱子B移到柱子C上去。(2)移动过程恪守下述规则:每次只允许移动一只盘子,且大盘子不得落在小盘子上面。(3)有人觉得这很简单,但真的动手才发现,如以每秒移动一只盘子,按照上述规则将64只盘子从柱子A移到柱子C上,所需时间也是很多年。*