056-尚硅谷-Scala核心编程-函数递归调用的机制.avi原创

对了，下一个我们就来看这个递归，朋友们，递归我刚才在前面讲过，特别的重要哈，我们来看一下递归是什么。呃，我们SC里面递归用的比较多，而且呢，呃，是这个马丁也推荐使用递归来解决问题，何为递归及一个函数在函数体内又调用的，本身就是自己调用自己。那么我们称之为递归调用，我们称之为递归调用，那现在呢，我们先请一个同学，请同学们先看一下这个代码。这个代码是写了一个函数接收一个N，如果N大于二，就TN减一。打印这个东西，我现在请同学们问一下这个地方输出什么。好的，请同学们思考两分钟。请同学们思考两分钟，待会儿我抽一个同学来说啊。

请同学们思考两分钟。现在呢，我找一位同学来说一下啊，针对这段代码，如果我们调用给他传入一个四，这边会输出什么呢？我找一个同学来。回答一下这个问题。回答一下这个问题。好，我找一位同学叫做咱们就近原则吧，就近原则叫中康同学来回答一下。你你也可以说不知道也行，无所谓。就是你你现在有思路没有。嗯。不，我知道打赢多次是肯定的，就是具体N等于多少打打N等于多少吗？这太的四嘛太的。是。三。

嗯，有。不同的结果吗？啊，有同学说是234是吧。是还有1234的是吧，好吗？这是434，这个算是一个111个阶段了啊，刚才有同学是234也有。还有说是1234的123。1234还有没有。不同的结果呀。那个那谁呀，你你什什么，你说什么姐22223个二是吗。二二还有没有？4322341234。222。肯定不可能全对吧，你又改了是吗？你又改了好同学们，这个呢，其实就是一个递归的最基本的案例啊，但是呢，肯定正确答案只有一个，不可能这么多是吧，那这样子我们先不去运行，我们先分析好不好，我们根据我们分析看看这个结果到底是什么来朋友们。

老规矩，现在呢，我们把这一段代码注意听，把这一段代码拿到我的这个，我就分析一次啊，我不会分析很多次的，就分析一次，那么我们的代码呢，老规矩开始从这里开始执行，尤其是不太明白的同学啊，我调用一个TEST4。当然这个T的是肯定是在主函数里面写的。对不对，好代码呢，主函数里面开始调用我们的T的四。好，现在代码呢，一到这儿我们来走一个同学们啊，这个东西对对你们来说特别的重要，我先说一下啊，递归这块，你你们将来这个肯定是会用到的。那么他一旦到太子的是根据刚才原先这个老师刚才讲的这个逻辑，他应该是这样走，首先呢有个主站。

这个我前面说过，主站里面呢，它会调用TEXT4。根据刚才我们讲解的这个原则。就是一旦有一个函数，就会开辟一个新的站。上面去，那么这个时候呢，会有一个站。啊，这个站呢，是test的站，这个站里面会传入一个什么呢？好，他一到这来代码就跑这来了。这个N会被接收到，也就是说在这个站里面有个N等于多少呢？就等于十。没问题，那么等于这个四过后呢，他就会在这个代码里面执行，他说N大不大于二呢，还显然大于二的。N大于二的啊，注意听，那这个地方可能有点不够，把它往下面拉一拉啊，因为有点不够。这个我这个站可能会往上跑。好，那呃，他这个时候N等于他今现在到这来过，N等于二就说。

NN4，四，N大于二是成立的，注意也就是说到这个里面它会去执行什么代码呢？执行这里面的代码能理解啊，这点大家一定很清晰的，那么现在你N等于四这个地方的N等于四，那么N大于二成立，于是它就会去调用test。N减一变成几了呢？变成三，那么变成三以后，注意这个print还不会输出。这个普特还没有机会输出。他马上又会开辟一个战。也就是说你刚才这个站它的调用是这样子，到这先开辟这个站。这个线啊，不好不好弄。画一个这个线，然后呢，当它执行到这个地方的时候，他又去调用这个站。太平行的站，注意这个这个地方还没带磁性，到这里面过后呢，又有一个台词的站。

那这个时候这个N等于几呢？等于三。因为你四进去嘛，三，那么等于三过后呢，他把这个逻辑继续再走，那么三大不大于二呢，三大于二是成立的，三大于三，四大于二嘛，然后你又去走这个test，于是变成二。注意，最下面仍然还有一个printer在这等着呢。等着呢，但是当他走到这一步的时候，他发现T的二是一个函数，于是他又开辟一个站。好，不着急，这个站。是把这个三下啊三下，然后这边这个站会干什么呢？它在这又到这儿来了啊，我把它标成一个这个绿线，然后这帮N变成了二二，好注意看。N大于二不再成立。N大于二不在这里，N大于二不成立了吗？于是他就去执行这个print，好，这个时候同学们可以看到就会执行这个N，这个地方会输出几呢？显然输出二一次，第一个结果二被输出。

好，我先记到这边啊，同学们。如果这个地方还没有过关，同学赶紧补啊，N等于二输出来了，当它输出来过后，我们都知道原先这个占占点已经到这了，当他这个一旦执行完毕，执行完毕过后，这个站呢，就相当于说执行完了，那么他这个站就回到这边来了，回到这儿干什么呢？回到这再执行下面这个print，那么请请问这个时候的print，他打印的N是这里面的N呢？还是他自己这这里面的N。使自己让你们，于是他又输出N等于几等于三等于三过后，这个是不是又执行完毕了，执行完毕是不是又下来了。好，因为你执行完毕，我就执行完了，自然就结束了嘛，他又到这来，到这来呢，他又去打印这个。Print。

大家这个print呢，这个边就N等于几了呢，N等于十。好，最后这个站结束主战结束主战一旦执行完毕，结束整个这个站全部销毁。啊，这个流程，因此这个结果是234，那刚才有同学说的是对的。有一个同学是234，这个同学说的是对的啊。刚才刚才有同学说的是234是对的啊，那么我们来看看是不是234把这段代码呢，给同学们放到这里来，我们把这个递归来聊了两句。好。我们在这里新建一个递归的包。来建一个包。好，这边看诶不在这啊，直接在这建就可以了，包的话在这里建。好，走一个啊。哎，这看这地方写错了。先把这个删掉。删掉啊。删掉包的话在这儿吧。

在这儿。Come，最直接chapter。CHAPTER05点，然后呢，这个地方叫。递归的意思or？好放进去，那放进去呢，我们把这个案例给大家拿过来写一下啊，DEMO01。DEMO写到这。好，同学们，那刚才呢，我们把这个代码就直接拿过来，这有个函数先拿过来，我就不再写了。在这边。Test。走一个，那我调动它test是。洗完了。我们执行看这个结果给我们分析对不对啊走运行一下。当我们运行完毕过后呢，我们发现这个结果是。234正确的，好，这是一个基本的原理，好这个完了，完了过后下面这个呢也很简单了，请同学们思考一下，如果我去调用这个TEST2也输一个四的话，应该输入什么？

把这个换成二。请问这个时候输出什么？哎，同学们刚才说的很对啊，只能输出一个结果，因为你这个结构是else了，那这个else你看刚才整个这个线，这个else的话，它除了在这个地方有一个机会进去，其他你其他是不是都是进到if才进去的呀，那只能在这个地方去打出个二，其他一个机会都没有。所以这个结果呢，就只能输出一个二，执行一下抛弃的结果，看效果。好，同学们可以看，只有个非常好啊，咱们班有些同学，呃，应该还是比较清晰的，有些同学可能这有点有点懵，但是我再多说一句，这个递归它是什么呢？它是后边你们学这个大数据用算法的时候会用到的常用的一个东西。如果你这个没有突破，那同学们，你们一定要想办法把它搞定。啊，但这个搞定呢，其实你只要把刚才老师讲的这个基本原理搞懂。

其他就是一个熟练的过程，好，同学们递归的一个基本介绍，我们先说到这里，我把这个板书再再把这个递归的规则说一下。那刚才我讲这个递归呢，讲完过后我要做一个总结，做一个什么总结呢，就是我们学东西啊，又说到学习方法了，就学完一个东西，很多同学是这样子的，学完就跑。啊，我也不不去总结，不做任何总结，我可以告诉大家，人的记忆力都是很很短暂的，我们每一个人的记忆力都是在一定时间能记住。你想一想，一年前你学的东西，你现在还能记得住吗？你根本就忘的差不多了。但是有些人很聪明，他干什么呢？他学完一个知识过后，他总结一下，在学完一个东西再总结一下，好，同学们，你们在总结中就会变得越来越强大。呃，我我叫我那个，我叫我的小孩，叫我小孩不是上三年级嘛，我就告诉他，你回来过后，你回来过后，今天老师讲了什么东西，你给我总结一下。

学除法像除法你们都都像你们都会了是吧。但是我问他，我说除法你怎么做的，他他就没有试，我说你这样子啊，除法第一步，第二步，第三步怎么做，你给我总结一下，诶总结完了过后，他说诶好像思路清晰了很多。如果我们不总结你会干什么，你会感觉到每天学到什么东西都根本都记不住。但是你总结哪怕只有几句话，哪怕只有几句话，你突然感觉到，诶，好像今天真的学了点东西，注意一定要总结啊，老师刚告诉你们东西，虽然不是不是说天天给你们整些这么高大上的东西，但是这些东西是你能够走的走的很远的一个基础东西，那么总结一下递归，根据刚才老师讲的递归呢，我总结这么几点，就是根据刚才讲的这个递归的一个规则或者原理，我总结了四句话，记一下执行一个函数时就会，就是当程序啊。当程序。程序执行一个函数时，就会创建一个新的受保护的独立空间及新的函数站。什么意思呢？就这。

比如说我们在这里一旦调用了这个text，它就会开辟一个新的空间，这个空间是属于占的。但是他的空间是独立的。这点大家能够看出来，第一点，第二点，函数的局部变量是独立的，相互不受影响。那将来你在做这个开发的时候呢，也有可能出现这么一个情况，什么情况呢？你传的不是这种基本值类型，你是传的一个引用类型，那如果传的引用类型的话呢，那也也可能出现这么一个情况，就说这有一个堆。这儿有一个堆。注意听这个堆。这个堆呢？这个堆。这个堆里面，可能你在这个主站，注意听这个主站。这个主站里边你有一个对象，你创建了一个对象，这个对象比如说奥杰。

但这个这个奥巴节呢，这个对象真正的数据在哪里呢？在这个堆里面。那也是有可能的，那这样子的话呢，你这个OB因为种种原因就指到这来了。直到这来，那在你这个递归过程中，你如果把这个OB传给了这个站，那么这个站呢，也有可能去指向这个站。好，甚至你在下一个这地方还可以进行这个站，大家如果有有印象的同学，你们应该学过那个抓。Two，可能现在大家学的少了啊，一般是学的spring mvc那个拦截器，它实现的底层机制就是把一个对象放在这，然后不停的开站，每个站都有机会去修改。这个对象，它底层的机制都是这么实现的，如果你学到这儿呢，就能理解是怎么做的，比如说小老鼠找迷宫，小老鼠找迷宫一个很经典的一一个题，他是小老鼠，它从一个入口开始，我这个案例在哪去了？我看现在可能找不到了，我看还在不在啊，如果在的话，我给同学们看一下。

我看看在不在，我我我看看在不在啊。这儿有一个什么小老鼠找迷宫，上午的资料。在这没没没没有准备到这儿啊。我以前好像记得，算了吧，先不去找这个了，我以前讲那个Java的数据结构的时候，跟他们讲一个迷宫回溯，就那个递归里面有好多地归，最终呢，每个老鼠，好多老鼠都在找迷宫，最终谁先找到就发一个信号，就在这个堆里面发一个信号，说找到了，大家都噼里啪啦退出来了。其实其实这个也也能实现这种这种这种这种效果好，这个呢，我先说到这里。啊，就是我们说的第几点呢，说的这一点什么呢？就是函数的变量是独立的，互相不受影响，如果你要受影响的话，是引用类型，第三点递归必须向退出递归的条件逼近，否则就是无限递归。

那比如说同学们看这里，看老师这边有一个代码，你看我这里为什么这边写了一个N减一。因为我只有N减一才会出现N不再大于二，这样才能退出。所以说你看这个递归里面有一个核心点，就是如果你没有一个像退出递归的这个条件逼近，那么这个递归一定是个死的。那跑不出来，你看你假如我这写成加号，同学们看这个地方肯定是死循环。啊，那我这掉错了，掉这他肯定是在不停的打东西，你看啊，我再给他跑一下，这个地方肯定是出不来的，你看这。你你看这直直接你看这这个地方还还还还在输，你看这这这你看这直接告诉你站一出了，为为什么站一出呢？就是因为你这个不停的开，不停的开，最后出现一个什么情况，就是这个站。

啊，不停的往上走，指走走走走走走，好多好多站死在这儿了。说你看这个为为什么说咱们写递归的时候，有一个特别重要的东西是什么呢？就是怎么去判断退出这个地位条件，同学们学过一个这个东西吧，我不知道大家学过这个东西叫二分查找习惯吗？二分查找是不是里面有一个条件就是要退出啊，哎，同学们，老师老师应该讲过这个东西好，第四一个当函数执行完毕或者遇到return时，就会返回，遵守谁调用就将结果返回谁给谁的机制，你比如说刚才我们写的这个东西，你看刚才写的这个东西，你你在这执行完毕后，这个结果会返回到哪里呢？谁调用我？我就返回，比如返回到这个位置。谁调用我就返回给谁好。这是函数的几个规则，我给同学们板述到这里。好的，那刚才我们讲的是什么呢？函数调用的一个规则总结。

好，写到这里来。哦，函数函数。函数调用啊，递归递归调用，调用的一个小结啊，或重要的重要的一个规则和小结。好，同学们，我把它呢，给大家整理到这里啊，整理到这里，那么这几句话希望同学们有一个。有一个印象。好。递归必须向退出递归的这么一个条件走。好，这是讲的递归的一个小结。我们总结啊，小。