递归算法及其实现盖州市第一高级中学赵广旺《算法与程序设计》教学内容◊递归的定义◊递归的要素◊递归的过程◊程序的实现《老和尚给小和尚讲故事》的故事从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听："从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听：'从前座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听........."，递归的定义（一）递归：参见“递归”递归：如果还不明白递归是什么意思，参见“递归。如何用递归定义正整数（1）1是整数（2）如果n是整数，n+1也是整数（3）只用通过（1）、（2）定义出来的才是正整数递归的定义（二）在函数、过程的运行过程中直接或间接地调用自身的算法就是递归算法。递归的要素递推公式：•通常把一个大型复杂的问题通过“递推公式（也叫递归方程）”层层转化为一个与原问题相同或相似的但规模更小的问题来求解。边界条件：•当通过反复的调用，把问题的规模小到一定程度时，必须能直接给出问题的解，即有明确的结束递归的边界条件（也叫递归出口）。计算n！（n的阶乘）计算过程：（手动推导）归纳总结n的阶乘的算法：n!=1(n=1)→边界条件n!=n*(n-1)!(n>1)→递推公式递归的过程递推阶段：•将原问题不断地分解为新的子问题，逐渐从未知的向已知的方向推进，最终达到已知的条件，即结束递归的边界条件，这时递推阶段结束。回归阶段：•接着从已知条件出发，按照“递推”的逆过程，逐一求值回归，最终到达“递推”的开始处，结束回归阶段，完成递归调用。递归的过程程序的实现递推公式边界条件定义函数程序代码例题：斐波那契数列斐波那契数列（Fibonaccisequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（LeonardodaFibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……用递归算法求斐波那契数列第n项的值。课堂小结把规模较大的问题变成规模较小的、规模较小的问题又变成规模更小的问题，当问题小到一定程度时，可以直接得出它的解，从而得到原来问题的解。即采用“大事化小，小事化了”的基本思想。递推公式→边界条件→定义函数其它程序举例（课后选做）汉诺塔游戏再见！
