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