05_尚硅谷_JavaSE面试题：递归与迭代.avi原创

Hello，大家好，我是上硅谷Java艺学科的讲师柴林燕，今天呢，我们想给大家分享一道面试题。只是一道编程题。有N步台阶，一次只能上一步或者是两步，共有多少种走法？那么我们呢，哎。有两种实现方式。第一种是递归，第二种是迭代循环。我要循环迭代。那么我们分别怎么实现呢？我们来分析一下啊这个过程。首先我们用递归。来分析分析一下，我们先把这个规律或者叫公式先推导出来。我们假设这个N等于一。我们呢，就可以走一步。那么得到呢？F1等于一。如果我们N等于二，那么我们呢，哎，可以一步一步走，或者是直接跨两步，这样呢，我们F2有两种，这个是比较少的，我们可以直接这个推出来，它最终的走法是多少，那等于三的时候，我们就比较复杂一点了，那么三的时候我们就想了，最后我们只能跨一步或两步，那我们就想如果我要最后一步跨两步。

那么我们就到达第一级台阶。如果我们最后想要跨一步，那我们就到了第二节台阶。那么我们呢，分别是这样子的啊，当你到达第一级台阶的时候，我可以直接跨两步上去，当你到第二节台阶时候，直接跨一步上去，那么这个呢。怎么到达第一级台阶，以及怎么到达第二节台阶，总的走法，那就是到达第一级台阶的一种，这么多种，到达第二节台阶这么多种加起来就是它了。因为跨一步或者两步嘛，加起来。如果你是四，同样道理，你最后一步是一步或者两步，那么到了第二节台阶的时候，我们最后一步可以跨两步上，第三节台阶时候我们跨一步上，因此你怎么到达这个的，我们累加起来，到达第二节台阶的总步数加到达第三节台总步数加起来，那么就是我们到达第四这台阶的总步数，以此类推，当X等于N等于X的时候。

我们呢，想办法到达X倒退两步的这样的一个位置，然后直接跨两步，或者倒退一步的位置，跨一步上去。那么总的走法加起来。那么这个时候我们可以把F呢当做一个方法或者叫函数一样的，那么这个呢就是N。那么可以来实现一下这个大。我们需要编写这样的一个方法F。它可以实现它的功能啊，这里就叫实现到这个F，我们刚才是N，然后呢，它的作用呢，就是求N部台阶。一共有几种走法，不管你的N是多少，我们都能给你算出来。那么比如说我们按照我们刚才推导的。

一跟二比较特殊，我们可以直接呢来实现它。那么if n等于一或者N等于二的时候，我们可以直接return n的值，因为这个一就是一种，二就是二种，那通过三开始，我们看三开始。那么就是用。F还是用我们自己的这个函数好吧，你有这个当N等于一的时候，多少九和N等于二有多少九加起来就是我的了，那么我们呢，可以是把这个呢。用我们自己的这个方法，F的N减二加上F的N减一，他这个方法的功能。第二个功能就是为了求N等于任意一个值，然后得到了一个总走法。好，这里如果你要再严谨一点，可以考虑一下N小于一的时候，我们呢，可以考一个异常，非法的参数的异常。

说N能不能小于一，可以这样考虑一下。那么我们测试一下这个对不对呢？Test，我们测试一下，它用这个词试一下，好，我们来看一下，打印一下。F1对不对啊。一种走法没问题，好，当我们是这个F2的时候，改一下是两种走法。当我们是三的时候。我们三种做法，三的时候对吧，一的时候很简单，二的时候很简单，我刚才说过了啊，跨两步或者是两个，那三的时候，我们呢，三步两步一步一步两步三步做法。

如果是四的时候呢。五怎么走呢？四。两步，两步或者一步，两步一步或者是。两步，一步一步或者是。一部一部两部。五种走法。这个是中间走两步，这是一开始走两步，这个是最后走两步的，这是我们的四，那它怎么走的呢？我们来分析一下它的运行的过程啊。看一下它的执行过程。我们呢，哎，Bug一下。第八个啥。执行的过程。好进到这个里面。这时候呢，我们看啊，现在F4我们要进到这个F4里面去。好，此时呢，N等于四，N等于四。

那么再往下走的话。不会满足这个条件，跨过一步。这个呢，也应该不会满足，不会进入这个if o的话就到这来，好，这时候FN减二它会怎么做啊，现在从这看我们的这个F，刚才这个N是四调用了一次，现在我们再进一遍。好，此时它又调用了第二点，但此时N是二。好，那么往下走。不满足小于一到这儿好，我们看一下往下走。它会进到这个里面去，因为A等于要满足好回来回来，也就是说刚才这个值它已经算完了。算完以后呢，也就是二了，然后呢，这边也是一样的，我们再进去。它又掉了一遍，这个是三。三是怎么走的呢？看一下啊，往下走，不满足不满足，好，此时又来到这个地方了。

来到这地方，我们看此时N是三，因此我们在进去的时候。这个是三减21，那就是N等于1F1算一遍，好，我们过来过来，那么也就是这个一好，这个FN等于三的时候啊，那么这个答案就是三减一，就F1等于一好，然后呢，右边继续看右边，那它这个呢，就。有这个我们刚才过来到这儿，那我们呢再来。好再过来是吧，我们的三嘛，三减一等于二嘛，好，我们看一下再来走。过来过来。N等于二，二呢，那就是212对吧，好，你看往下走到这来了，我们呢，就是N等于三的时候，把这个呢算出来了，一跟二我们回来，那就是得到了我们的三，这时候刚才只是算了这半边。

好，这个呢，二那么加上我们刚才的三，那么再回来就是我们的五了。是这么来算的，也就是他要调用很多遍的这样的一个，呃，我们打印出来啊，等于五我们结束回到我们这边。他调了好多遍。掉了好多遍，当F4的时候进来，那么F2走一遍加上F是吧，F3走一遍，那F2呢，再下去就直接回去了，那F3回去又导致了我们的F1加上F2，所以呢，你这个方法就在这。一次是吧，这一次这这有一次。调了好多遍，然后最终得到了这个结果。也就是我每一个这样的走法对吧，然后分解出来对吧，然后它又分解出来，可能有好多种走法，好多种走法是吧，是从倍数二的N次增加的，所以它的这个效率呢，不是特别高，如果你啊看一下我们来测一下时间，给他测一下时间，Start等于system current。

See current many times。来测一下时间，这我的end，我们打印一下这个时间的话。And减去start，好，我们把这数改大一点，比如说改成十。我们看它的时间是。嗯，应该还比较快，那我们再改大一点，比如说五十四十吧。好，那么我们呢，这个时间啊，注意40是这样。这是毫秒，毫秒。好，这是我们的这个值，过来40，这是递归实现的方式。但是它的阅读性比较好啊，就是我们这个步骤，你看从这公式当中直接就写出来了，所以它这个实现方式上面，代码编辑上比较简单，但是可能在理解它的这个运行过程，或者说它这个效率上是不好的。

那么可以呢，换一种做法，其实它这里就是反反复复的重复一些事情，那因此呢，我们可以啊，用循环迭代就可以重复做一些工作，那么怎么分析呢？我们来分析啊，首先F1对吧，也就是我们N等于一的时候还是一样，那么我们这个比较直接，没有特别多的当等于三的时候哈，我们刚才分析出来，它是从第一级台阶跨两步和第二节台阶跨一步，因此我给。它设定两个变量，One保存的是最后走一步，就是前面的所有的步数。To就保存最后走两步，前面所有的这个步数，那么我们加起来，那根据我们刚才经验，他正好是，哎，走到第一级台阶总步数跟第二节台阶总步数加起来，那因此我们的two呢，哎相当于就是这个了，我们的one呢，相当于就是这个啊。

好，那么同样道理，如果是四，我们呢，也是想办法到了第二级，然后呢，从第二节跨两步，想办法到第三节跨一步上去，那因此它也是最后走两步或者是一步。那么我们呢，得到的这个就二跟三了，那也就这个to呢，就正好是我们啊，这个走两步的所有的步数，这个one呢就走三步了。好，就是往前这个推，就是我们一直在不断的修改这两个变量的值，修改这两个变量的值。好，那么这样的话，我们呢，N等于X呢是一样的，那么这个to呢，就修改为前面两次的这样的一个，那万呢前面一次。那怎么去实现它呢？我们来写一部这样的一个代码。好，我们重新来一遍。Test啊，然后呢，Step。触吧，第二种。

好，我们同样的啊，要写这样的一个方法。嗯。啊，我们的，为了区别，我给他呢放了名字啊，循环loop。前面不变，这个不变。对吧，一样的这个单独这个比较特殊值，最大值不变，好，接下来我们说要设置一个变量，它主要我们是从第三。不开始第三个台阶以后，开始听到的规律，那么我们呢，哎说这个，呃，我们的Y等于怎么呢？哎，我们的Y呢，等于我们的啊这个F2 f2那是多少呢？就是我们的。两级台阶处，哎，我们就是一级台阶，就是走到啊，这个走到低一级。台阶的这个啊。步，这个叫什么走法？

这初始化值啊，初始化为好，然后呢，我们初始化为走到啊第二题。第二节台阶的走法，好，那我们这里面呢，就再来一个啊，总的步数，总的步数。好，我们就要sum好了，那么我们如果等于三的时候，那我们some呢，应该是等于啊这个to啊，然后呢，加弯，最后走两级台阶，因为我们要从这个二级。我们看一下啊。从这个二级是吧，走两步。Two不是从第一级跨两步上去吗？跨两步上去，哎，跨一步上去。分别就是最后。最后画。跨两步加上最后跨一步一步的走法。

就是我们总的做法，比如三的事。那么我们不光光是这个，那么因此我们循环I等于三开始以后都是这个规律，小于等于N，然后呢，I加加爱加加好，我们每次都是最后走两步和最后走一步，但是这个one two不是说初始化这个值得改，也就我们的to啊，得变成什么呢？我们的这个往前倒推一吐啊，就往前倒推一步。哎，倒退这个两步两步的做法，那因此呢，我们呢，就是这个。我们的上一次的那个，那么to呢，等于我们的这个。要最后走两步嘛，它是要最后走两步，那走两步的话，我们呢，相当于等于上一次的这个呃，万，而我们的万呢，最后走一步，那么就是我们上一回的some。

下一回的上。因为some就是我们在下一个sum，就是他再走多一步的。这个效果，那最终呢，Return我们的sum，那是不是这样的呢？我们来再测试一下public，来把我们这个测试的代码粘过来。穿过来啊，那么同样的道理，只不过这回呢，调用的方法叫做loop了。好，我们还是先把这个时间的这个去掉啊，先把我们的这个1234先测一遍，一练习一下。2:0。三运行。这都是正确的，四看是不是五种啊，跟他们有关。好，那么我看我们如果是40种。

我们看看时间上啊，以及这个我们的。结果上对不对。结果上是一样的，但他的时间非常非常把它小于一毫秒。调一毫秒，所以说我们这个的效率会。更高一点，但是这个的可读性比那个呢，要差一点点啊，所以呢，我们总结出来啊这个。用递归，那么我们是方法自身调用自身，如果用变量，就是用原来的这个纸推出新的纸，就是它一直在不断变化这个变量的值，那么各自的优缺点，这个呢，大问题主要是小问题，可以减少代码量，同时代码非常精简，可能性非常好，但是它浪费空间，因为它不断的调用自己方法，当我们啊这个多一点的时候，就容易照出这个这样的一处，而我们这个迭代呢。这个代码不够简洁，可能性不好，但是这个没有额外的时空的开销，好，那我们看一下啊，如果我们如果用迭迭代跟这个递归，我们弄多一点啊，比如说我们弄成100。

我们看一下。他的时间上就会非常非常的长了。非常长，你再大一点身子，这个站就溢出来了。好，那这里呢，就而我们这个的话，用循环的，比如改成100。哎，但是呢，它这个值已经超了int的范围啊，但是它时间算出来非常快。所以说我们各自的优缺点啊。好，今天呢，就讲到这里，谢谢大家。