6.5.2 递归定义和调用过程在线视频

刚才咱们说到了

从前有个山　山里有个庙

庙里有个和尚讲故事

这种古老的故事

函数的递归调用

正像是这个故事这样

你中有我　我中有你

下面我们就从

一个具体的问题开始介绍

函数的递归

如果

我们要求一个非负整数

n的阶乘

例如n为4

那么

这个问题就

可以从数学的角度来分析

4的阶乘

应该等于

把它写成一种算法

那就是

4的阶乘

等于4乘上3的阶乘

3的阶乘

又等于3乘2的阶乘

所以

这个算法

应该包含了解决如下两个问题

第一

如果

n的值为1或为0

这时候

阶乘的值就为1

如果n大于1

那么

n的阶乘就应该是

n乘上n-1的阶乘

把这种算法

可以描述成

这样的数学公式

那么

用我们前面学过的函数的定义

我们就来写一段功能函数

来求一个整数n的阶乘

大家看

在这

我们定义一个功能函数

函数类型为浮点型

函数名为fact

整型变量n

作为函数的形参

在这个函数体中

咱们定一个浮点变量f

就是来

获取求得的阶乘

因为是非负整数

所以

如果n小于0

我们给出一个出错的提示

如果n的值为0

或为1

把1赋给f

否则

就将n

乘上

以n-1为参数

调用这个功能函数

把乘得的结果再赋给f

函数调用结束

返回f的值

从这个函数不难理解

求阶乘这个算法的实现

这段函数还提醒我们

在这个函数的定义中

出现了函数的调用

也就是说

一个函数自身调用了自己

这个就是递归

那么现在我们来看

递归的基本概念

递归调用就是一个函数

直接或间接的调用了它自身

称为函数的递归调用

简称递归

递归函数的执行过程

又是什么样呢

我们下面

还是以刚才这个求阶乘的例子来看

如果咱们编写一段主函数

在主函数中

我们输入一个n的值

假如我们输入的是4

以n为形参

调用功能函数

此时

程序的流程就转到了这个

求阶乘的函数

4

作为实参

传给了

功能函数中的形参n

按照我们刚才的分析

这个程序运行的结果

就将函数返回值f

也就是4的阶乘

代回到主调函数中

赋给y

其实

编写一个求阶乘的递归函数

可以有不同的方式

就像我们刚才写的这个

我们管它叫阶乘函数1

大家看这个函数

在这个函数中

咱们定义的是浮点变量s

作为求得的阶乘

与刚才不同的是

此时的边界条件为

当n为0的时候

0的阶乘为1

那只要不为0

我们首先将

n-1为参数的函数调用结果

赋给s

然后让s再乘上当前的n

再赋给新的s

以此来求得

当n为参数的时候的阶乘

假定

我们现在以n为4为例

来看一下阶乘函数2的调用过程

是什么样的

大家看

当实参为4的时候

进入函数体内

首先判断边界条件

那么此时n不为0

程序执行

以n-1为参数

调用函数

那此时的参数为3

这时

程序的流程就转向了

递归函数的

下一次调用

也就是

以n-1　n的值为3

为参数

调用这个递归函数

在这次调用中

同样首先判断的是边界条件

此时n不为0

程序执行

将此时的n-1

也就是3-1为2

以2为参数

调用这个递归函数

函数开始下一次的调用

当n的值为2时

首先判断边界条件

那么不为0

又转向下一次

以这时候的n-1

也就是以1为参数

再一次调用

递归函数

n为1

同样要判断是否符合边界条件

刚才我们说了

这一个函数中边界条件是为0

所以

此时仍然执行的是

以当前的n-1为参数

又开始下一次的调用

那这时候

再次调用这个递归函数

n的值为0

很显然满足了边界条件

将1赋给此时的s

程序转向最后一个返回语句

返回到哪呢

显然

主调函数调用被调函数之后

返回到主调函数中

调用被调函数的

位置

向后继续执行

因此我们现在看到

当n为0调用完阶乘函数之后

程序的流程返回到

当n为1的时候

继续刚才的语句之后的语句执行

这时

在这一个函数中

n的值为1

乘上返回值1

得到了

在n为1为参数时的s

那么同理

当n为1

函数调用结束

函数的返回值将返回到

上一层调用

也就是n为2为参数调用时

那个位置

继续前面的语句

得到了

n为2时函数调用的返回值

依此类推

n为2函数调用结束

返回到它的上一层

也就是

n为3

在调用递归函数时的位置

继续后续语句的执行

所以此时

将返回值2乘上

在这个函数内的参数

n为3

得到的是s的值为6

那么执行这条返回语句

将

返回值6

代到

上一层调用

也就是n为4时

调用这个递归函数

将返回值6乘上当前的n

也就是4

得到的最后的4的阶乘为

24

由此看来

函数的递归就是这样

那么我们对递归作以下说明

比如我们看右侧这图

我们一开始用n为4

来调用函数

在n为4调用函数过程中

有用到了以3为参数

调用功能函数

那么这些同名的变量

n为4　n为3

n为2等等

每次调用

它们占用的空间是不同的

显而易见

就像我们刚才看到的

当n为0那一次调用结束

获得了返回值

s为1

这时返回到上一层

那么同时

程序取得

当时进入那一层时

函数中的变量和形参

所占空间中的数据

这就是

在递归调用中的

变量的存储空间的

占用的情况

和返回的情况

刚才我们说的求阶乘

是一种数值类的递归问题

这类的问题

我们还可以有一些例子

比如说

在我们学循环的时候

大家学过一个

斐波纳契数列

也就是说

求一个数列

根据我们前面的分析

我们解决这个问题的思路就是

首先这个是一个数学的问题

是一个数值类的

递归的问题

那么对于数值类递归的问题

我们首先设法

找到解决这个问题的数学公式

那么不难看出

这个序列中的第n项

等于它的前两项之和

也就是

这是第一步

第二步

这个问题怎么结束

也就是说

我们要找出递归的结束条件

很显然

当n的值为1

和n的值为2的时候

FN的值就为1

根据以上的思路

我们就可以编写

下面的这段程序了

我们定义

这一段功能函数的

函数类型为长整型

定义函数名为

fib

整型变量n为函数的形参

当n的值小于等于2

函数返回1

否则

就返回同名调用这个函数

以n-1为实参

再加上同名调用以n-2为实参

那这个就是

解决斐波那契序列中

第N项数值的递归的算法

从这可以看出

结束的条件就是

当n小于等于2的时候

返回值为1

通过以上分析

我们总结一下

编写的递归程序的要点

那么前两个例题

都是数值类的

对数值类的递归问题

可以表达成数学公式

那我们就从数学公式

推导出这个问题的递归的定义

也就是

算法之中的具体的步骤

然后确定问题的边界条件

从而找到递归的算法

和递归的结束条件

了解了递归的基本的定义

和递归程序的调用过程

我们就多做一些例题来看看

首先我们从c语言的运行环境中

来看看求阶乘

和求斐波那契数列的

第N项的应用实例