222-尚硅谷-Scala核心编程-使用递归的注意事项和陷阱.avi原创

就是我们书上呢，经常有人说递归一定要慎用，我觉得的确如此啊。来，朋友们，我现在以求一个飞波纳气为例。来给大家讲一下这个递归的注意事项是什么地方，那么我们先来看一下这个递归，求斐波拉奇代码应该怎么写，同学们应该还有一点印象，来吧，打开它，我们叫rivers s。Rivers，然后呢，斐波纳我就简写了啊，斐波纳斐波纳七呢，他是一个人哦，是一个挺厉害的一个什么数学家还是干嘛的啊，反正挺厉害，然后就纪念他，就把它数列呢，命名为斐布拉奇数列，那么我们来求这个斐波拉奇数列呢，我就直接写个函数了。这个对我们来说很简单，我写个F非波纳斐波，那然后呢，我接受一个N，这个呢，我我写成big int啊表示将来会很大，返回呢，也是一个big int，好斐波那系数大家以前学过的就是如果N呢，它等于一呀，或者N呢等于这个二，就返回几啊返回一对吧，A应该怎么办呢？就是斐波那。

斐波那去N减一，再加上一个斐波那斐波那，然后N减二。这样子的，好了，同学们，我们现在来玩一把，看看这个东西会出现一个什么有意思的现象呢？当我传一个。穿一个山进去，我们看菲波拉西应该是1123。五好同学们以此类推，那么如果我给一个三，它就返回一个二，这个应该没有任何问题，速度很快，啪的一下就出来了。啪的一下就出来了，来看二好，现在我们再给他传一个十，速度也会很快。也会很快。你看我说，但是问题来了，我们来研究一下，当我们这样去使用这个斐波纳气阶层来处理这个求职的时候，我们看看它的这个调用的次数，就这个递归的次数，它是如何增长的，这个地方一定要小心，我们来研究一把。

我们研究。研究一下这个普通的写法啊，研究。研究下这个递归球，这个非呃斐波纳器，斐波纳器速的呃，一个调用次数的调用啊，递归次数吧，递归次数的这个增长。你会发现非常的恐怖啊，大家稍微一动脑筋，同学增长的这个这个这个这个情况。啊，我们来看一下情况，比如说我现在在这整一个这个数，我在这整一个数啊，我们来把这个数传进去。呃，怎么怎么整呢？为了研究这个问题，我干脆把这个函数拎到里边去，因为我想给他传一个全局变量去测试。好的同学们，我先在这里面写一个非常大的数啊，Va VR count等于。

呃，六一个big in吧。六一个big int，那么初始化给他来一个零。诶B的是直接写就行了是吧，啊直接写就行了，不需要用用他的一个apply方法，那么这个时候呢，我调用一次，我就给他加加。这个不犯法吧，我加下一，然后呢，我在这打一句话说调用递归的次数是递归的次数。递归的次数是把它加起来。呃，然后呢，我输出个count，我们来看一下啊，如果我传的是三这个递归的思路，大家一看就看出来了，很简单，应该就调用了三次。没问题，好，这个很很正常，我们如果执行四次，我们求四，你看它的调用次数变成五，这个也很正常，好我们来整五次，整五次的时候，你会发现次数就开始增长越来越快了。

五是九次再来看啊，当我们六的时候，当六的时候，这个递规的次数变成多少了呢？15次，好，我们来吃狠一点的，直接20次，我们求二次，你们看一共掉递归多少次呢。你们看递归一共是一万三五零，这个大家注意第11的时候啊，求十的时候，它的递归次数是这个，然后我来求一个21，我只涨了一个。我只讲了一个，同学们可以看到这个调用次数的增长特别的恐怖。他只有2万次了。知道为什么？因为在这个地方，你们去思考一下，它整个一个11过后里面它会重复计算。你看也就是说你增加了一，它就变成这么多，它几乎是呈这个倍数增长。这个就很可怕，那有时候老师可怕在什么地方，当你是当你是30次的时候啊，你们看他会按照一一两千万次的次数的这个增长，你看30万是这么大，大概是1000个十百千万十万吧，一千一千六百多万，当我整到呃三百一百一百六十六万是吧，160万好31好，这个就很恐怖了，你看啊。

刚才是160多万200。200多好，你等到你掉到这个数的时候，你这个程序已经跑不起来了，看掉40次，同学们，你看这个代码应该会卡在这了。卡死了。40之一卡死了。要等好多次呢，这个地方你想想递归能这么用吗？递归就不能这么用，那么什么样的递归它就不出现这个问题呢？各位同学啊，我这个就不等了，这个要可能要等很久。哦，我也没去等过，我就不等他了，那么这个地方我们可以看到这种方式呢，它会呈现一个指数性的增长，就是递归的次数。

递归的，递归的次数呈呈现呈现啊是是指数增长，指数增长，那个增长它会很恐怖，那为根本的原因其实在于你这里面会有两次调用。两次调用你看啊，如果我我就这么一个意思啊，假设我们来看，如果我们这地方不是有两次调用，而只是一次，它就不会指数增长。那么我们我们也用这个来测一下，刚才我们求这个，求这个值，求这个阶层，我们来统计它的次数，你会你发现他的次这个增长呢，就会你增加一个，它就增加一次，这种递归它就非常有效。那么我们来看看求阶层和这个最大区别在什么地方呢？我这样写啊，斐波，那我就我就这样子假设，我就写一个具体的数吧，我就。

但是现在我我我准确的讲不是这个菲波拉七了啊，非不是非波拉气了，我我们来看看这个时候它的次数是多少。就是因为我们有掉两次，你看这个次数。你看这个是20次，看到没有，你原先是多少次，现在噌的一下就降到20次了，你你那个40次的话，可能是几千几千万次的调用吧，结果你看这你再来个50。你再来个50，你看它调用多少次。你看得用多少次地柜才多少次。地柜才25次。所以说这里面最大的问题大家要去想，如果你们在写这个递归的时候，你一定要考虑，当我们在这个递归地方会出现这个重复计算时。重复啊，重复计算时，大家就要考虑优化，大家需要考虑优化，那么这个优化的优化的这个原则，优化的原则是什么呢？来说一下优化的原则一般就是改递归为迭代。

迭代，或者是想办法减少这个递归的字数，那么这里面有篇文章，同学们呢，晚上去看一下，这篇文章呢，写的还是不错的，它是一本书上的，他专门讲了对斐波纳切的一个优化，一共有好好多种方式啊，好几八九种吧，我没去看看一下。他这个关于斐波拉奇的优化，那么这里面我们简单看一下啊，我也不去看那么多，看第一次优化。迭代了，他直接改迭代了，也就是说这个时候他就没有用。递归了，然后呢，下面呢，你看这个地方继续优化，就是优化的第二种方式，呃，又一种，这又是一种。啊，这个又是一种。这个地方呢，它仍然用到这个递归调用，但是呢，优化的比较好。他仍然用递归，但是这种递归就非常的非常好了，次数降低，然后下面还有还有第七种。

还有第八种以及第九种。那么越到后面呢，这个越。不太容易看懂的，它是递迭代加递归结合使用，那么我这里主重，因为我这儿不是讲算法。以后呢，我估计这个我这讲完这个课程过后呢，呃，学校会给一个任务，就是专门录一套讲这个数据算法的，到时间录完过后给大家分享一下就行了，那这个地方呢，它涉及到很多优化的方案，有些呢是需要数学功底的啊，但是呢，没有关系，只要我这里讲这个主要是告诉大家递归可用，这是没问题的，但是你在。递归掉的时候呢，你要防止它的一种重复计算，你比如说前面我们这几个，你看刚才求这个最大值，其求这个最大值，还有求这个求这个反转，你看这个反转，它就这种写法，它就绝对不会出问题，因为它只有一次。它不会出现问题，再如说我们求这个呃阶层，它速度也会很快，你你就是写个特别大数速度，你看啊，假设我写一个这么大一个数，它仍然会很快就返回，那么我们打出来一个结果数，这个结果可能是可能打不出来啊，我不知道能不能打出来，这个相当大，看他能不能打出来。

第一个特能打出来吗？我天他他他也不行了哦，他也他也不行了，但是不是不是这个我们把这个整小一点哦，3000。因为它是一乘到3000，这个数太大了。好，直接爆炸啊，这个数它存不进去了。在300。300估计也不行，也不行，太大了。太大了，30 30难道也不行吗？还是很大是吧？这个也还是越界了，来个20，因为不止这么大一个数。哦，我知道我这里方问题是没用big in，我说怎么回事啊？哦，没有说用big找我说big也不至于这么小啊，我这忘写了啊。改成改成big，应该这个书应该能撑下来啊，应该能撑下来，应该这做了转化了。

你看这个数还是很大的，来整一个50，你看速度很快对吧，因为你这个递归它，它的次数并不多嘛，你看一下就出来了，咱们整个500。哦，500看有有多庞大一个数啊，看big in的能不能撑得住。他他还真撑得住了，这哥们啊，这个数就真撑住了啊，太恐怖了，这个B跟一还是很牛逼的，他跟底层用了些，呃，不是简单单的一个数的存放，肯定是字符串进行一个处理了，好不管怎么样呢，这种你看它不会出现这个问题，假设你敢这么写一下，你就死定了啊老师，我们玩一下这个呗。我们来整一个这个N减二，这就有重复计算了，那你这个就我估计会死在这啊。啊，你看这个地方不知道怎么大，跟50就就该就就撑不住了，整个三十三十看看会出现个什么情况。啊，这个地方可能就你看这就直接也就炸了，他还没他还没停下来呢，啊，这就直接炸了，好就是我说的一个道理呢，大家应该理解了哈，就是要小心小心这个，那么同学们可能会想会想这样一个问题，说老师我们能不能有一种有一种学科专门来研究我们的代码，它的执行的效率，以及它递归的次数呢？有有一门课程以后同学们可以去学一下，叫数值分析。

数值分析呢是一个就是专门研究算法的程序员必学的一门课程，叫数值分析课程。啊，他专门研究你的代码，这个就说你的代码它的一个执行的效率高低，就说两个代码不用执行，我就能通过数字分析来看谁的效率更高，因为他主要是看你这个调用的次数，他能算出来。到底是按什么样的一个规律来增长的？好，OK，那这个呢，我们就先聊到这里啊，可能聊的不是说的不是很多，但是因为我们后面还有很多很多内容，并且呢，这个递归呢，它也不属于SC纳的一个内容，我只是抛砖引玉，讲到这给大家提了一些，大家呢有兴趣再去看那个数字分析和一些其他的内容，好，我写到这啊郭同学，那么这个地方呢，我提出了一个观点，就是使用递归的怎么样一个注意事项。

哦，使用递归的一个注意事项，大家呢，在这种开发的时候，脑海里面呢，一定一定要有这根这根弦在脑海里边，不然的话代码可能会出大问题，哦，代码可能会出大问题，好，这是老师分析的一段代码，那么我把这个代码呢，给各位拿过去啊，这段代码就会炸啊，我们就写到这里。写个20。好的，那这是我们讲的这个注意事项，截取一段视频。