day09_面向对象(上)/22-尚硅谷-Java语言基础-递归方法的举例

那我们再来看一个例三。那例三那个后边呢，这放了这样，这个其实咱们刚才做了啊，看一下这道题吧，这个呢，如果大家觉得这个有一些难度，你就先放一放啊，先放一放啊。说呢，已知一个数列，嗯，这个零的时候呢是一啊，一的时候是四，然后后边呢，有这样的一个关系式，就是这个数它依赖于它前面的这个数和他在前面这个数的一个关系，假设现在让我们去计算F10，哎，这个是多少？这个要是手算的话会吧。会手算应该会是吧，哎，你这个，呃，这是你要想算十，这就算九，这算八，然后九跟八你再接着往下算，呃一直呢，倒到这个已知的这个方向，那现在咱们看一下用递归怎么写啊，Public int，不妨呢，我就叫做F了，Int这个N。

进来，哎，他说什么咱们就写什么啊，说如果N呢是零，哎，我这呢就RETURN1。Else if，哎，如果呢，N是一，我家呢就RETURN4啊，然后else。那否则否则什么呢。Return多少？有没有人这样说的哈，说return呢？这不是你要求的是FN嘛，那就把这个式子往左一移，说returnna叫F啊，N加二啊，减去这个二倍的啊，这个N加上一，这不就是你得到这个FN吗？这样行吗？这就麻烦了。

哎，你看这不FN就等于这个式子减这个式子吗？我现在求的不就是FN吗？这样写这样写，你看这个问题是什么哈，我现在来这儿去测试。哎，这个我整一个这个换行的哈，现在呢，咱们通过这个test，哎，我现在去调一下，这个叫F，我放它上，求求谁F10行，我这写个F10。诶，然后执行啊走哇，挂了这个挂的这个错误的信息叫什么呢？还叫战役出还叫战役。怎么理解？你看我要算十，这两个都不满足，是不是蹦到这了？我要想算F10，那你就得需要去算F12，再减去二倍的F11 f12不知道，我想算F12 12呢，就得算F14和减去F1013，然后14又不知道再往上算，这个数越算越大，是不是离这个越来越远呀？那就永远不可能终止了啊，那就挂了。

啊，这一出呢，这个咱们提过啊，你每次掉自己这都是一个新的变量，占空间都去得给你定义这个N啊这个定义N了以后，你里边又掉了一个，它也销毁不了，又得新造一个，真的都销毁不了，导致呢就溢出了。这个不能这样写哈，应该怎么写，对，你应该是把这一项当成叫FN，哎对，这个呢叫N减1N减二，所以呢，就是RETURN2倍的FN减一加上FN减二，诶这样才靠谱啊，那就意味着我们想算十，这呢就是二倍的F9加上F8，九不知道九进来，九呢，就这样这样算一下啊，这是十，我现在得需要九，得需要八，哎九的话呢，哎，右翼进来，哎它的需要八跟七，哎然后这呢也也是类似的展，哎八跟七的话呢，就需要七跟六，哎这个需要呃六跟五，然后接着啊这个五跟四这块也一样，展展展展，一直就展到这个零跟一这了，然后再整个翻回去。

这样这样出来了。啊，这个翻回去，这都不用你管，它自动的就往回翻的，所以很多时候我们做这个呃循环问题的时候呢，呃，有的时候循环反而不好解决，当我们用递归的时候，你会发现这个题目呢，一下子很简单，当然这个缺点呢，就是它有点难度，你可能不好想到。哎，你好像不好想到啊，哎，这个题的话呢，其实就这样写，哎，然后呢，这块我们，哎做一个输出，看一下结果，诶这个诶哎这个我们掉了以后呢，没有去获取啊说in特一个value。

哎，打赢我们这个Y6。哎，这就是这样一个结果啊，行，嗯，这道问题的话呢，这个大家呢，就是应该能稍微感受一点，就是你要用循环写的话呢，可能也得花点精力去写，你要用这个递归的话呢，其实这个代码量非常简单，非常简单啊，那其实呢，那还有一个问题，这个我们就说一下就行哈，那就是提到的叫费纳切数列，这是一个非常经典的一道问题，那费纳切数列的话呢，就是我下边写的这个描述，这就是一个斐布纳切数列啊，斐布纳切数列呢，满足这样一个关系哈，它第一项呢是一，第二项呢也是。

之后，哎，之后呢，每一项呢，就等于前两项的和。哎，这一项就等于它和它相加，就是二，这一项呢，就是等于前两项的和一跟二三，然后五呢，等于二跟三相加，就是每一个数都等于前面一项和再前面一项的和。啊，这就叫做斐布拿解数列啊，这个我家的那个那个WiFi呢，就用的这个大密码，其实是很容易被破译的是吧？当然呢，会比较显得高大上一些啊，每当有朋友过来说说你家密码是多少呢？我说斐摩纳奇数列的前这个七位啊，他一下子就蒙圈了，你知道吗？啊这个啊哎，这就是它，这叫斐拿解数列，这个数列的话呢，你看比如说有一道数学问题，数学问题大家呢，不知道有没有听过哈，说呢有N阶台阶，N阶台阶，然后这个人呢，从最底下呢，他要登这个台阶了，说呢他呢只能每次呢登一个台阶，或者每次登两个台阶。

对，然后问说呢，我登完这N阶台阶一共有多少种这个方法再说一遍啊，N阶台阶呢，每次他只能踩一个或者踩两个啊，然后呢，我把这N节台阶走完，一共呢大概哎不是大概了，就一共准确的话呢，应该有多少种不同的组合方式。啊，这个你要自己做肯定发现哇，这个还是有点难度的，实际上它就是斐布拉切数列。我想计算FN，就是一共有多少种我就需要呢？我说就是N减一加上FN减二。为什么我想这个问N阶台阶有多重，那我就是假设我现在是N减一这块，我现在站在这儿了，我是不是没得选，只能一脚过去是吧，所以这就是你N减一有多少种，我这呢，就是对应的这个直接就是这是一种情况啊，因为你每次只能是踏一节或踏两节，那我就把这个你弹一节，这个只要N减一的情况再考虑一下这个N减二的，N减二的话呢，它现在在这。

按说呢，它可以踏A节或者踏两节，但是你要抬A节的话呢，其实就蹦到这块了，所以就不能重复计算了啊，那你N减二的话呢，只能是踏两步过去，其实就相当于把这个呃，N减一的加N减二的加起来，就是你FN这个式子的话呢，咱们刚才这个做过三了，你发现这个这这比三还还简单的，嗯，这不就相当于这是N这个二，把这个二去掉不就完了，这个改成一就OK了，哎，所以这个题目的话呢，呃，你要是分析清楚了，N阶台阶一共有多少种走法，其实比这道题还简单。啊，但是呢，你能想清楚这个事儿啊，有一点难度啊，这个还比如说大家呢，呃，听过这个汉诺塔是吧，汉诺塔的话呢，呃，比如说这是有两个，这是比较简单的情况啊，哎，他呢想让你把这个呢转到这块，转的过程当中，你可以借助于中间这个塔，它的唯一的要求就是这个塔你在转的时候呢，你呢就是不能，哎对，你不能把这个大的放上边，小的放下边，就这一个要求。

你要两个的时候呢，比较简单，就是把这个呢，先把这个小的你放这儿，大的呢先扔到这儿，把这个小的呢再扔过来，这就算成了，三个的时候呢，比它就要难一些啊，三个就要难一些，那四个就更难了，五个呢就更难了，五个就有点可能快搞不定了是吧？实际上这道问题你分析分析的时候呢，它其实也是可以用递归来完成的啊，这个题目的话呢，你可以去网上去搜一搜，我我就不给大家整了哈，有兴趣的话你搜一搜，这个题呢，如果用递归来完成，其实也非常的简单，然后呢，每次变化的步骤你加个c out，你这个N呢，即使是十，那就是有十个这个塔块，十个塔块以后的话呢，一运行你看他那每一步骤就写出来了，他让干什么你就干什么，那一定可以转成。

啊，用递归写非常简单，就是递归呢，它也可以解决咱们的这个循环的这样的问题啊，就是咱们除了能够用for和while之外呢，递归也可以做，但是呢，这个递归它确实要难一些，有的时候呢，大家想不到。啊，这就是它的一个点啊，那那目前的话呢，大家先能见过啊，确实知道这个结构就行，包括呢，咱们，呃，这我写的这个再来一个呢，就是例五例五。诶例五呢，刚才提到了一个，这个叫汉诺塔问题啊，哎，这个我就过了啊，然后例六，例六呢，咱们提到叫快排，哎快排的时候呢，咱们里边也是出现自己掉自体了，为什么会出现这个呢？我们首先呢，取它的第一个元素，把后边这元素呢分成比它小的和比它大的，分完以后这个呢，它就跑到这儿了，这边就比它小的，这边是比它大的，然后剩下的这块元素仍然是取出第一个元素，再把这块分成比它小的比它大的，你会发现这个操呢翻来覆去的做，那不就相当于自己叫自己吗？我就把这个选选选第一个元素，把后边的元素选成比它小的，比它大的做成一个方法，那就相当于翻来覆去的就掉一个方法，就是自己调自己，直到呢，你这个呢，不能再分了，终止啊，这就是朝着一个已知的方向去执行的。

啊，那这块一说的话，那比咱们前面讲的那个，呃，这个流程控制啊，数组啊，那块排序啥的那个就更难了啊这是叫递归这块的一些问题，哎，大家知道这个方法内调方法就叫递归，哎，也简单的看到这样的几个例子就可以了。啊，就行了啊。