ok，那么在了解了递归调用的过程以后

我们就来看一下递归的作用。在这个部分我们要

介绍三种递归最常用的三个场景。先来看第一个，就是用递归来

完成递推。这什么意思呢？不着急，我们先来看一个例子。

还记得这个例子吗？切饼。

就说一百刀去切一个饼，问你最多可以切出多少块？

这是我们以前在从iii问题到计算机程序那个部分举的第一个例子。

那么当时呢我们对这个例子是这么来解的。因为啊

第0刀的时候这个饼是一块的。然后第一刀的时候呢在第0刀的基础上多了一块。

第二刀切下去多了两块。第三刀

切下去又在上一刀的基础上多了三块。

第四刀切下去多四块。也就是说第n刀

切下去就会在前一刀的基础上增加n块。这是饼的块数增加的一个规律。

那么按照这个规律呢我们曾经写过一个程序，在这个程序里头我们用了

一个循环来计算那么切到n刀的时候

我们能得到多少块。这是当时我们所写的程序。那么现在呢我想让你考虑一下。

我们可不可能利用递归来解决这个问题。

那如果想用递归来解决的话我们应该怎么思考呢？

好我们来分析一下。你看我们现在所采取的这种思考问题的方式，我们是从最简单的情况开始。

也就是说我们思考问题的方向是从切第0刀第一刀第二刀

一直向切第n刀的方向去考虑的。

也就是说从i=0的情况向着i=n的情况去考虑。

所以我们才得出一个用循环来解决这个问题的

办法。那么现在呢我希望啊我们能把这个视角转换一下。

我们直接去看第n刀和第n-1刀有些什么样的关系。

比如说我们可以这样来思考。假设

我们切下第n刀的时候我们得到的是q(n)块。

当然虽然我不知道q(n)这个值到底是

多少，但是呢根据刚才那个规律我却知道

q(n)跟q(n-1)存在这样一个关系。它就等于q(n-1)加上

n。那么其实这个式子已经给了我们足够多的信息了。

因为这个式子清晰的表达出来了q(n)和q(n-1)之间的

递推关系。也就是说只要有了这样一个表达式那么剩下的

信息不需要我在程序里头逐一体现。

有了这个式子以后其实那个递归关系就已经建立起来了，比方说我们知道了q(n)=q(n-1)+n

我们也就知道q(n-1)就等于q(n-2)+n-1。

那么也就知道q(n-2)跟q(n-3)之间是什么关系

等等等等。那么q(1)跟q(0)之间是什么样的关系。

这个式子就已经统统都告诉我们了。所以说我们的关注点

只要放在这个式子上面就可以了。有了

这个式子底下的这些递推关系我们根本就不需要

逐一的去体现。当然要想解决这个

问题除了能够表达递推关系的这个关系式以外我们还必须再获取一个信息。

那就是当n处于边界条件下的时候函数的返回结果。

也就是说我们必须还得知道当n=0的时候q(0)

等于1。那也就是说只要有了这两个条件，其实

关于这个问题的解决方案的所有信息我们全部都

掌握了。那么利用这样一个信息我们就可以写出解决这个问题的逻辑。

也就是说当我们切n刀的时候能得到多少块呢？

我们假设当我们切下n刀的时候我们能获得q(n)块。

那怎么去求解这个q(n)呢？那我们就可以通过这样一个关系去求解。

只要n不等于0

那么这个q(n)就等于n加上q(n-1)。

那么这里呢给出我们的第一个信息点。那么当n=0 的时候应该怎样呢？应该return

1，就是当n=0的时候函数的返回值是1。这是我们提供的第二个信息点。正如刚才我们讲过的

有了这两个信息点那么程序就可以去运算了。那么借着

这样一个递归函数很容易我们就可以写出整个递归程序。那么这儿呢是我们定义的q函数。

那么在主程序里头呢我们直接调用了这个函数，并且打印了这个函数的

值。当然这个时候呢当然作为一个测试呢我们去计算一下n=4的情况。

那么关于这个程序的执行情况我们仍然可以利用这样一张

图来表示。有同学说哎呀你怎么老是去用这样一张图啊？ok

那么这个图呢确实是我在这个课上给出来用它来表示函数之间调用关系的这样一张图。

那么这种表示方式呢比较简明，特别是对于复杂递归的情况啊用这种方法表示出来之后啊

会变得容易理解。那么大家在分析问题的时候啊也可以使用这种图

来帮助自己做一个分析。ok我们来看一下这个调用关系。

Main函数先运行，运行到中间呢它调用了

q(4)，于是呢我们把它标定在这里，q(4)就开始执行。

那么当q(4)执行到这一句的时候它就会去调用

q(3)，当然q(4)还没有执行完。

在没有执行完的情况下它就会去调用q(3)，那q(3)呢再开始执行，又

执行到这一句q(3)又会调用q(2)，那么当q(2)再执行到这一句的时候呢又会调用q(1)。

那么q(1)呢也是执行到这一句的时候呢就会调用q(0)。当然

我们反复强调在这个调用过程中你最好把每次调用都想象成

开辟了一片新的全新的内存空间。这样才能保证

你的对应关系不会乱。当q(0)再去执行的时候还会执行到这一句吗？

哦不会了。因为q(0)呢在这里就会进入if的这个分支，最后呢返回1。

于是呢q(0)就带着它的返回值1

返回到调用q(0)的那个函数

q(1)。q(1)呢在调用q(0)之前执行到这一句了，但是它还没有执行完。

它在这个地方等着q(0)的返回值呢。

所以说当q(0)带着这个返回值1

回到q(1)的时候那么q(1)呢接着去执行这一句。

那请问在q(1)中n等于多少？n就是这个参数，所以说这个地方是

1。于是呢q(1)会计算一个1+1=2。然后呢q(1)带着这个

2返回它的调用者，也就是q(2)。

那么q(2)呢也是在它的这一句上等着q(1)呢。

那q(1)返回2以后q(2)去用它自己的那个

n以q(1)的返回值2相加，于是2+2得到4。

那么当q(2)计算出这个4以后呢q(2)也就执行完毕了，于是带着这个4返回

q(3)。那么同理q(3)呢把它的内存空间中的那个n与q(2) 的返回值4

进行相加，于是呢3+4获得7。当得到7以后呢q(3)也执行完毕，于是带着7返回了它的

调用者q(4)。那么q(4)呢也把它的空间里的n跟这个7进行相加于是得到

11带着11返回到Main函数。于是Main函数呢在这里

打印出q(4)返回的这个11。

所以整个程序的执行结果会打印出11。

这就是这个函数的执行过程。那么透过这个执行过程我们可以看到

虽然这个图很简单，但是啊它可以帮助我们来进行一个比较清楚的

分析。ok，那么通过这个例子呀我们就可以看得出来

其实呢我们可以利用递归这

种方法来解决具有递推性质的问题。

比方说切饼，那切饼就是一个典型的具有递推性质的一个

问题。我们就可以用递归程序来解决这样的一个问题。

那当然啦在解决这个问题的过程中我们必须要注意递归和递推的不同。

首先递推的关注点往往是在问题的起始点上。就是说它会先去关注i

等于0的情况。然后呢从i等于0的情况向着i等于n的情况慢慢地

去推理。然而呢递归程序

不是这样的。要写一个递归程序的话我们的关注点

必须直接的放到求解目标上，也就是说我们会直接的去考虑

i=n的情况。然后呢找出i=n的情况下

应该如何去计算函数的结果。

这就是递推和递归最大的一个不同，它们的

它们看待问题的视角是完全不同的。

当然它们两个之间也有非常大的相同，那就是说它们两者都非常的

关注。函数的第i次执行和第i+1次执行之间的

关系。那么通过这个程序我们可以感受到其实用递归来实现具有递推性质的这种问题呢是有它的优势的。

它可以让程序一下子变得简明了很多。

那么对于一个普通的问题，我们怎样才能找到那个合适的递归函数呢？

那在这儿我们对这个方法稍微做一个小总结。

如果我们想使用一个递归程序

来实现或者是解决一个具有递推性质的问题的时候

就需要我们做这么几点工作。第一个呢我们需要把关注点直接放在

要求解的那个目标上。那么直接对这个目标进行分析。

所谓的目标也就是说i=n的情况。在这个基础上呢我们再去找到

这个函数的第n次执行和第n-1次执行之间的

关系。找到那个递推关系。然后呢我们再去确定第

1次执行的时候返回的结果是什么。那么有了这三个条件呢我们就可以

写出我们的递归函数来了。这就是当我们使用

递归的方法来结局具有递推性质的问题的时候应该使用的一种思考方法。

ok，那为了让大家对这个方法有更强烈的一个感性的认识，我们再来看一个程序。

看这个数列。我们来观察一下。

这数列是这样的。1，1，2，2，3，5，

3，5，8，5，8，13。通过这个观察

我们就可以看到这个数列里头任何一个数字

都是它的前两个数的和。

其实这个数列呢就是非常著名的Fibonacci（斐波那契）数列。当然这样一个数列在很多的状况下我们都会用到。

很多人喜欢把这个数列当作密码来使用以至于

很多的网站那么拒绝接受这样的一种密码。

ok，那么现在呢我希望你写一个程序

来求解斐波那契数列的第n个数字将会是多少。

首先我们非常明确，斐波那契数列呢是一个递推数列。

那么现在呢我希望你使用一个递归的程序来计算这个数列的第n个数

到底是多少。那么根据刚才我们总结的，我们看问题的视角

不从第一个开始。我们要直接放在第n个数上。既然它是一个

Fibonacci数列，所以说我们就可以得出来第n个数跟第n-1个数之间具有什么关系呀

是不是它就有一种这样的关系呀？第n个数其实就等于第n-1个数和第n-2个数的和。这是我们站在第n个数的

角度去考虑的第n个数和第n-1个数之间的这种

关系。那我们找到了。那么接下来呢我们还需要再去寻找

最简单的情况下就是当n=1的时候会怎样。

那么对于Fibonacci数列呢就必须要考虑 n=1的情况和n=2的情况。那么对于Fibonacci数列呢

这两个情况都已经预订好了，它们都等于1。

于是呢我们就可以基于此来写出一个递归的程序。那么这个程序呢也非常的明确。

对于Fibonacci数列中的第n个数如果n=1或者是n=2的话

那么这个数列将都会返回1，因为它的前两个数

都是1。那么除此之外呢Fibonacci数列的第n个数就等于

这个数列的第n-1个数和第n-2个数的

加和。其实这个程序逻辑描述的就是刚才我们所得出来的那个逻辑。那么就用这样一个函数再去写

程序我们就非常非常的简单了。

ok，这是关于如何用递归来解决具有递推性质的问题。

递归应用示例（切饼、斐波那契数列）

C程序设计进阶

与讲师见面