一、递归函数的理解1、生活中的递归生活中“递归”的典型例子就是“问路”。如图，小哥进电影院后找不到座位，问旁边的小姐姐，“这是第几排？”，小姐姐不知道，就问了一个一个向前，向第一排的观众提问，然后依次反馈。结果，“我在第一排”，“我在第二排”，……，最终确定了你的座位排号。在这个过程中，充分体现了“传递”（查询）和“返回”（反馈）的思想，所以这种现象称为“递归”。2、编程中的递归计算机有两个特点：“笨”和“非常快”。因此，将“复杂问题”转化为“多步骤的简单问题”后，计算机就可以高效地执行。递归是一种编程算法，它通过调用自身来简化一些复杂的问题，从而很容易找到解决方案。下面通过一个简单的案例来理解编程中的递归案例：计算1+2+3+4+5+6的和。functionfn(n){if(n===1){return1;}return+fn(n-1);}fn(6);计算过程：f(6)=6+f(5)f(6)=6+5+f(4)f(6)=6+5+4+f(3)f(6)=6+5+4+3+f(2)f(6)=6+5+4+3+2+f(1)f(6)=6+5+4+3+2+1从上面我们可以看递归函数的本质：一个调用自身的递归函数的实现有两个要素：终止条件是逐渐接近终止条件情况下的终止条件是：fn(1)===1当n===1、如果没有终止条件，函数会继续计算f(0)、f(-1)、f(-2)···从而进入死循环，得不到结果。从计算过程可以看出，函数依次计算f(6)、f(5)、f(4)、f(3)、f(2)、f(1)，满足第二个元素步逐步接近终止条件。2.递归函数的使用通过上面的讲解，你一定已经明白了递归函数的原理，那么递归函数是怎么写的呢？如何使用递归函数解决实际问题？实例探究递归函数的编写“套路”实例：计算阶乘的n。第一步：找到终止条件，写成if数学知识：n！=n*(n-1)*(n-2)*(n-3)*···*3*2*1显然终止条件是n===1;,return1;所以函数的前半部分可以完成：functionfn(n){if(n===1){return1;}//未完待续}第二步：求函数的等价关系公式，写为returnmathematical知识：n！=n*(n-1)!通过数学知识n！=n*(n-1)!而递归函数的本质（调用自身），可以得到函数等价关系f(n)=n*f(n-1);这样就可以完成函数的后半部分：functionfn(n){if(n===1){return1;}returnn*fn(n-1);}至此，简单的递归函数就写完了。递归函数最大的特点就是代码简洁（简洁到让人心虚）。总结一下，写递归函数的“套路”1、找到终止条件，写入if2。找到函数的等价关系表达式，写成return3.递归函数的问题肯定是你会说上面两个例子用循环就可以解决了好写，为什么要用递归？其实可以用递归解决的问题也可以用循环来解决！而且递归比循环慢，因为递归需要逐层调用函数，占用系统内存，当递归层次很深时，性能消耗很大，往往不推荐使用。问：递归是什么意思？递归就是把复杂的问题简单化，为解决问题提供思路，进而得到“循环算法”。对于简单的问题，“循环算法”一目了然，但是对于抽象的问题，通常可以先采用递归思维，比如：例子：一个人需要走10步，有两种走法，走法A：一步一步走；走法B：一步两步。两种行走方式可随意交替使用。有多少种方法可以走到第10级台阶？很难直接看到这个问题的循环解法。我们不妨尝试从递归的角度来解决：当走到第10步时，只差最后一步时，有两种可能：第一种：从第8层->第10层（两步inonestep）第二个：从第九层->第十层（一步一步）假设：从0层—>8层，有x种移动方式；1,1,1,1,1,1,2,21,1,1,1,1,2,1,21,2,1,1,1,2,21,2,1,2,2,2·······//列表是无穷无尽的，一共有x种，每个方法的最后一步是2（步）假设：从0级—>9级，有y种走法;1,1,1,1,1,1,1,2,11,1,2,1,1,2,1,11,2,1,2,2,1,11,2,2,2,2,1...总共x+y种行走方式。因此，10步=9步+8步，即f(10)=f(9)+f(8)；所以我们需要的函数关系是f(n)=f(n-1)+f(n-2);接下来求终止条件：当有1步时，只有1种行走方式（1步，1步），当n===1;时，返回1;2steps踩的时候只有2种走法（2次1步1步或者1步2步），当n===2;,return2;由此我们可以写出递归函数functionfn(n){if(n===1||n===2){returnn;}returnfun(n-1)+fun(n-2);}如下图展示了函数的执行过程。可以看出函数在执行过程中被多次重复调用。相同的功能（相同的背景颜色），极大地消耗了系统的性能。经测试，这个递归函数最多可以计算到f(45)；左右（测试需谨慎），这是递归函数的主要问题。那么如何优化这个问题呢？即把递归算法改成循环算法。通过前面的推导，我们知道f(n)=f(n-1)+f(n-2)；1步==>走法：12步==>走法：23步==>走法：1+2=34步==>走法：2+3=55步==>走法：3+5=86步==>方式：5+8=137步==>走法：8+13=21...即只要知道前两项（步骤1和步骤2）的结果，您可以从下到上计算所有后续项目的结果。所以可以写循环函数functionfn(n){if(n===1||n===2){return;}varleft=1;//左边的数据varright=2;//左边的数据rightvarsum=0;for(vari=3;i<=n;i++){//循环从第三项开始sum=left+right;//计算前面左右数据的和left=right;//上一个右赋值给下一个leftright=sum;//把上一个赋值给下一个右}returnsum;}以上就是通过递归的思维逐步简化抽象问题，从而得到循环的过程算法。循环算法解决了递归消耗系统性能的问题，可以计算任意值。（当值过大，超出JavaScript取值范围时，返回Infinity）四、总结1、递归结构简单易懂，常用于简化抽象问题。2.递归必须有终止条件，否则就变成死递归；3.递归算法运行效率低，性能消耗大，递归深度大（不能等待结果）时慎用；4.大部分可以用递归解决的问题都可以用循环来解决。
