序设计的一种实现技术，涉及递归定义的证明通常采用数学归纳法。Р若给出阶乘F(n)=n!的递归定义：РF(0)=1???????递归基础РРF(n)=n×F(n–1)，n=1，2，3，…??递归步骤Р?可以据此给出其Raptor程序实现：РР2. 迭代Р“迭”是屡次和反复的意思，“代”是替换的意思，合起来，“迭代”就是反复替换的意思。在程序设计中，为了处理重复性计算的问题，最常用的方法就是迭代方法，主要是循环迭代。Р迭代与递归有着密切的联系，甚至，一类如X0=a，Xn+1=f(n)的递归关系也可以看作是数列的一个迭代关系。可以证明，迭代程序都可以转换为与它等价的递归程序，反之，则不然。就效率而言，递归程序的实现要比迭代程序的实现耗费更多的时间和空间。因此，在具体实现时，又希望尽可能将递归程序转化为等价的迭代程序。Р前面介绍的阶乘F(n)=n!，其迭代法Raptor实现如下：РРР下面再介绍一个容易被误判为递归的迭代实例——猴子偷桃问题。猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就多吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半多一个。第10天只剩一个桃子，求第一天共摘下来多少个桃子？请设计一个程序求解该问题。Р假设an表示第n天摘下的桃子数量，分析可以得到第n-1天摘下的桃子数量为an-1=2(an+1)，通过此递推公式得到每天的桃子数量如下表所示：Р天数nР1Р2Р3Р4Р5Р6Р7Р8Р9Р10Р桃子数量anР1534Р766Р382Р190Р94Р46Р22Р10Р4Р1Р递推方向Р← ← ← ← ← ← ← ← ← Р递推也是一种迭代，但是往往被人误以为是递归（递归是自己调用“自己”，递推不是）。因此，使用Raptor实现上述猴子偷桃问题，其迭代程序（递推程序）如下图所示：
全文预览
