第七章 函数(三)

发布时间:2024年01月05日

二、函数递归调用

1、函数递归调用的定义

所谓递归,就是指函数的递归调用,只不过这是一种很特殊的函数嵌套调用,为什么特殊呢?因为它是自己调用自己,向己调用自己导致了很多初学者觉得递归调用很难,很不好理解,实际它并没有那么难以理解。

例:

在 main 函数中,调用上面的 diguifun 函数,把程序执行起来,可以看到,屏幕不断滚动并输出下面的内容:

有的编译环境可能会出现报错,崩溃,异常退出等,根本原因是系统的资源(内存)耗尽了,这是因为不断无限次地调用函数自身所导致,调用函数是要占内存的,每多调用一次函数,系统的内存就要多占用一些,当函数调用完成,从函数中返回时,调用这个函数时所占用的内存才能被系统释放掉。

例:

上面的nesttingFun1中定义了一个变量a,在nesttingFun2中定义了变量b,这个变量a要在nestingFun1执行完之前才释放内存,这个变量b要在nestingFun2执行完之前才释放内存。不光是这些局部变量,在函数调用过程中,可能还会存在函数参数需要临时保存,一些函数调用关系,(例如 nestingFun1 调用的 nestingFun2,nestingFun2 词用的 nestingFun3)也要记录,这样函数调用返回的时候,才知道返回到哪个函数里。对于函数嵌套调用来讲,只需要记住,系统会给函数调用分配一些内存来保存提到的这些信息(局部变量、函数参数、函数调用关系等)。但分配的内存大小是固定和有限的, 一旦超过这个内存大小,程序执行就会出现报错、崩溃或者异常退出的情况。

如图:

这个例子导致函数自己不断地调用自己〈递归调用) ,造成了调用的死循环。调用这种自己调用自己的方式必须要有一个出口,这个出口也叫作递归结束条件,有了这个递归结束条件,就能够让这种函数调用结束。

2、递归调用的出口

这里用一个范例来解释递归词用的出口。

递归设计思路:

(1)找重复:思考问题规模如何缩小

(2)找变化:变化的量往往做为参数

(3)找边界:就是递归出口

例:计算5的阶乘,也就是1*2*3*4*5的结果值。

这个题可以用循环来计算,也可以用递归调用来计算。

阶乘递归设计思路:

(1)找重复:n的阶乘 = n * (n - 1的阶乘),那么 求 "n - 1的阶乘"就是原问题的重复

(2)找变化:这里就是n的量越变越小,变化的量往往做为参数

(3)找边界:就是递归出口,找一个数的阶乘,不可能小于1

分析:

(1)4 的阶乘* 5 就等于 5 的阶乘。

(2)3 的阶乘* 4 就等于 4 的阶乘。

(3)2的阶乘*3 就等于 3 的阶乘。

(4)1的阶乘*2 就等于 2 的阶乘。

(5)根据数学知识,可以知道 1 的阶乘就是 1。

根据上面的分析,如果要用递归解决求 5 的阶乘的结果问题,那么要知道这个递归调用的出口在哪里。这个递归调用的出口就在 1 的阶乘这里。因为:

(1)1 的阶乘是 1,可以作为出口,能够求出 2的阶乘,也就是 1*2。

(2)2 的阶乘知道了 ,就能够求出 3 的阶乘,也就是 2 的阶乘* 3。

(3)3 的阶乘知道了,就能够求 出 4 的阶乘 ,也就是 3 的阶乘* 4。

(4)4 的阶乘知道了,就能够求出 5 的阶乘 ,也就是 4 的阶乘* 5。

最后,就得到了 5 的阶乘的结果, 5 的阶乘的结果是 120 。

递归函数代码如下:

在 main 函数中,调用计算 5 的阶乘的函数。如下:

尽管递归函数jiecheng的代码行数不多,但会发现这些代码不好懂。可以通过设置断点逐行跟踪调试的方式帮助自己理解。

思路:

(1)第 1 次调用jiiecheng 函数会执行 result=jiecheng(5-1)*5,第1次调用处所在代码行的信息被暂存,然后进入jiecheng(4)。

(2)第 2 次调用jiiecheng 函数会执行 result=jiecheng(4-1)*4,第2次调用处所在代码行的信息被暂存,然后进入jiecheng(3)。?

(3)第 3 次调用jiiecheng 函数会执行 result=jiecheng(3-1)*3,第3次调用处所在代码行的信息被暂存,然后进入jiecheng(2)。?

(4)第 4 次调用jiiecheng 函数会执行 result=jiecheng(2-1)*2,第4次调用处所在代码行的信息被暂存,然后进入jiecheng(1)。?

(5)第5次调用 jiecheng函数,jiecheng(1)的出口条件成立了,result=1,能够执行 return result;这行了,这可是 return语句第 1 次得到执行。

第1次return 1,返回的是1,返回到哪里了?

返回到了jiecheng(2),result= 1*2,并且也执行了 return result;? 返回了1*2=2,返回到哪里了?

返回到了jiecheng(3),result=2*3,并且也执行了 return result;? 返回了2*3=6,返回到哪里了?

返回到了jiecheng(4),result=6*4,并且也执行了 return result;? 返回了6*4=24,返回到哪里了?

返回到了jiecheng(5),result=24*5,并且也执行了 return result;? 返回了24*5=120,返回到main函数去了,打印出结果。

上面的例子演示了递归函数调用的出口,出口必须有,否则就会陷入递归调用死循环,导致系统资源耗尽而使程序运行崩溃或者异常退出。这个出口相当于循环语句中循环结束的条件。

练习:

1)顺序打印 i 到 j ( i <= j , 包含j)

顺序打印递归设计思路:

(1)找重复:顺序打印的话,i每次要+1

(2)找变化:就是i的量越变越大,变化的量往往做为参数

(3)找边界:就是递归出口,i=j就是出口

先打印i,再递归执行下一个。

2)倒序打印 i 到 j ( i <= j , 包含j)

执行时先执行子函数,再执行父函数。

3)对数组 arr 所有元素进行求和

文章来源:https://blog.csdn.net/weixin_30479905/article/details/135415235
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。