数据结构笔记总结(4.4)递归运行的机制:递归的微观解读

递归的微观解读

之前一直在强调书写递归算法的时候一定要注意递归的宏观语意,站在一个更高的层面去思考函数本身的功能作用是什么可能可以帮助我们更好的完成递归逻辑。

但是从另外一方面递归函数到底是怎样运转的呢?机制是怎样的也是必须了解的。

在之前学习栈的应用的时候,我每次曾经学习过栈有一个非常重要的应用就是“程序调用的系统栈”。

也就是我们在一个函数中调用子函数的时候,子函数调用的位置会压入一个系统栈,当子函数调用完成后,程序就会在系统栈中找到上次父函数调用这个子函数的位置。

然后在父函数之后继续执行。其实递归调用和这种子函数调用没有区别,只不过调用的这个子函数还是函数本身而已,下面用具体例子来说明一下。

数组递归求和

首先看一个简单的例子,对数组求和,为了演示方便,将最后的return拆成三句话

下面来看一下具体这样一个递归调用到底发生了什么。

我们调用只有两个元素的数组,也就是arr=[6,10],求第0个元素到最后一个元素的和,调用sum(arr,0)。

首先就进入了第一句话,if(l==n) return 0;,此时l等于0,l等于n显然不成立,进入下一句话,int x =sum(arr,l+1);,此时产生了一次递归调用,即又调用了一下sum,其实就是调用了sum(arr,1)。

然后在一个新的sum函数里,重新针对现在这个参数转一遍,这就是递归调用和子过程调用的区别,a调用b,其实就是在b里转一下逻辑,a调用a其实就是在一个新的a里转一下逻辑。

当前原来a中所有变量保持不变,当新的a转完了逻辑,我们还要回到a去转,如图,在这个新的sum中,l取的就是1了,同之前原理,继续执行到第二行,调用sum(arr,2)。

此时,第一行语句成立,直接return 0 了,这个0就返回在上一次中断的位置,此时x=0,之后sum(arr,1)这个函数继续向下执行,res=10,下一步,将这个res=10返回上一次中断位置。

继续执行sum(arr,0)的第二行代码,此时x=10,往下执行,res=16,此时程序结束,因此我们得到的最终结果就是这个16.

递归删除元素节点

下面来看一个稍微复杂点的例子,就是之前删除元素节点的例子。对于这个例子,整理成三句话来看,模拟调用这个函数,对于6–>7–>8–>null,如果我们删除7这个节点,那么这个递归的过程是怎样的呢?

由于这个函数代码比较长,所以我们给代码编上号,分别是1,2,3共三步。

对于每一次调用,就用这三步来表示执行到了哪里,这和我们编译器调试递归代码有点像,由于递归函数只有一个,当你走进这个递归函数后,通常是重新进入你写的这部分代码。

虽然从代码的角度来讲是在重新执行这些逻辑,但是你已经是针对一组新的参数来执行这些逻辑了,和之前的递归调用时不一样的。

下面这个过程,暂时不用文字解释,检验一下自己,如果自己能看懂了,那递归也就掌握的差不多了。

[v_error]递归调用是有代价的:函数调用+系统栈空间[/v_error]

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(4.4)递归运行的机制:递归的微观解读

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多