3.3 迭代与递归

在人们生活中经常会碰到这样一种情况，一个问题刚刚开始感觉难以解决，但是可以尝试将其简化后再解决。如果解决问题的过程可以重复进行，那么需要解决的问题最终会变得容易处理。计算机就是用来解决人们生产生活中遇到的相应问题的。在计算机程序设计中，处理这样需要重复的过程引出了两种不同的处理方法：递归和迭代。

3.3.1 递归

1.递归简介

递归算法是将规模较大的问题归结为规模更小的同类问题的子问题，子问题可再分解为同类的更小的子问题，直到最小子问题能够直接得到答案，或者非常容易解决。而且，这些子问题的解决都可以采用同一个模型，然后层层返回，得到原始规模较大的问题的解。

以求前1、2、3、…、250个正整数的和为例，原问题可以转化为250加上前249个正整数的和，现在只要求得前249个正整数的和加上250就行了。与原问题相比，现在问题的关键依然是求前多少个正整数之和，问题的本质没有变，不过，原来需求出前250个正整数的和，现在只要求出前249个正整数的和即可，问题的规模变小了，难度降低了。经过层层分解，问题最终可以分解成求前1个正整数的和，我们知道前1个正整数的和为1，求出了前1个正整数的和就可以求出前2个正整数的和，通过层层返回，就可以得到前250个正整数的和。

递归算法过程可以分解成递推和回归两个阶段。在递推阶段，把规模为n的问题求解分解为规模小于n的问题求解，依次减少一个或几个元素，直到规模n=1或0时，能直接求解。然后回归，推出n=2时解，推出n=3时解……直到n的解。递归在分解子问题时必须有一个明确的出口。

在C语言中实现递归需要用到函数，递归就是一个函数在其定义中直接或间接地调用该函数本身的一种方法。现在定义一个nsum函数用来求前n个正整数的和。

求前1、2、3、…、250个正整数的和可以写成nsum（250），可以分解为250+nsum（249），前249个正整数的和可以简化为249+nsum（248）……前1个正整数的和为1，就是nsum（1）为1。可以得出下列递归公式：

求前 n 个正整数的数，C语言的递归的nsum函数定义如下。

下面以求前4个正整数的和为例讲解递归执行过程，即nsum（4）执行过程如图3.6所示。

当需要求前4个正整数的和，也就是执行函数调用nsum（4），是第1次调用nsum，先进行形实结合n为4，再执行函数体，因n==1条件不成立，执行“return n+nsum（n-1）”，即“return 4+nsum（3）”。于是需要求nsum（3），中断第1次调用nsum（4）函数执行，进行第2次调用nsum，形实结合n为3，执行函数体，因n==1条件不成立，执行“return n+nsum（n-1）”，即“return 3+nsum（3）”。需要求nsum（2），中断第2次调用nsum（2）函数执行，进行第3次调用nsum，形实结合n为2，执行函数体，因n==1条件不成立，执行“return n+nsum（n-1）”，即“return 2+nsum（1）”。下面第4次调用nsum，形实结合n为1，执行函数体，因n==1条件成立，执行“return 1”。第4次调用nsum执行完毕，返回结果为1，程序返回到第3次nsum函数，继续执行“return 2+1”，返回3，第3次调用nsum（2）处理完毕，返回结果为3。程序返回到第2次nsum函数，继续执行“return 3+3”处，返回6，第2次调用nsum（3）处理完毕结果为6；程序返回到第1次nsum函数，继续执行“return 4+6”处，返回10，第1次调用nsum（4）处理完毕结果为10，也就是求出了前4个正整数的和，完成了问题的求解。

2.递归应用

有一群猴子，去山上摘了一堆桃子，商量过后它们决定每天吃剩余桃子的一半，在它们吃过桃子后，有一只贪嘴的猴子又偷偷地再多吃一个。按照这样的方式，猴子每天都快乐地吃着桃子，直到第十天，当猴子再想吃桃子时，发现只剩下一个桃子了，问：猴子们开始一共摘了多少桃子？

分析：设x1为第一天桃子的数量，x2为第2天桃子数量，

则x2=x1/2-1，变形为x1=（x2+1）*2,

设x3为第3天桃子数量，

则x3=x2/2-1，变形为x2=（x3+1）*2。

由此类推，fun（n）为第n天的桃子的数量，fun（n+1）为第n+1天的数量，

则fun（n）=（fun（n+1）+1）*2。

当n=10时，f（10）=1;

得出下列递归公式

用C语言编程如下。

执行流程如下图3.7所示。

3.3.2 迭代

迭代本是数学中的一个重要方法，只是随着计算机科学的快速发展，借用计算机运算速度快等特点，迭代思想逐步演化为迭代算法。其基本思想如下：让计算机对一定步骤（或一组指令）进行重复操作，在每一次执行这些步骤后，都能用变量的旧值（初值）计算出一个新值，通过新值的逐渐变化，达到（或逼近）最终结果的目的。

以求前1、2、3、…、250个正整数的和为例，可以先求出前1个正整数的和，这个结果很容易得到为1；在前1个和的基础上加上2求得前2个正整数的和；再在前2个和的基础上加上3求得前3个正整数的和；后面不断重复该操作，直到最终求得前250个正整数的和为止。

迭代是一种建立在循环基础上的算法，在设计过程中需要考虑怎样由前一个数得到后一个数，也就是迭代公式是什么，还要考虑什么时候终止迭代，也就是重复迭代的条件是什么。在求前250个正整数的和例子中，若 sum 表示前 n -1个正整数的和，那么前 n 个正整数的和就是 sum + n ，将 sum + n 赋值给 sum ，这时 sum 就表示前 n 个正整数的和，可以写出迭代公式“ sum = sum + n ”。 n 表示1到250之间的某一个数，初值为1，每次将 n 累加到 sum 里，将 n 变成后一个数，即“ n = n +1”，直到 n 大于250为止，即重复迭代的条件为“ n <=250”成立。下面用C语言完成迭代法求前250个正整数的和。

小结

通过本章学习，使读者知道什么是计算机程序，了解计算机程序设计思想的发展历程，体会怎样用“自顶向下，逐步求精”解决复杂的问题。理解递归法和迭代法解决问题的思路，认识计算机解决问题的特点。

习题

1. 结构化程序的特点是什么？

2. 程序中的常见控制结构有哪些？

3. 用迭代法和递归法求出求斐波那契数列的第 n 项。