js递归函数的含义和经典例子

1.js递归函数的含义

    js递归函数是一类特殊的函数类型，简单理解即为在一个函数的内部调用了该函数自身。在使用递归函数是需要注意产生递归的条件与递归终止的条件。如同循环控制语句一样，没有递归终止的条件，程序将会一直占用资源，无法结束释放资源。递归函数的说明可以从阶乘的计算这一案例展开说明。阶乘计算过程描述如下：

阶乘计算过程描述如上图所示，我们可知阶乘问题的解决主要在于递推关系的挖掘与终止条件的确定。本例中递推关系为N!=N*(N-1)！，终止条件为1！=1；在明确这两点之后我们可以编写递归函数实现问题求解。递归函数描述如下：

<script type="text/javascript">
     function f(n) {
       if(n<=1) {
         return n
       }else {
         return n*f(n-1)
       }
     }
     console.log(f(6)) //输出720
</script>

2.经典递归问题举例

     爬楼梯问题是使用递归算法进行问题求解的经典案例之一，爬楼梯问题主要只是假设有N阶楼梯，需要从最底层爬到最高层，在上楼过程中每步只允许上1层或者2层，计算爬到N层总共方法有多少种？

爬楼梯方法问题采用递归思想还是比较简单的，我们可以从小人最后一步考虑。小人上到最高层N层时只能有两种方法：

①从N-2层跨越2层到达N层；

②从N-1层跨越1层到达N层；

则计算到达N层的方法f(n)就等于到达N-1层方法f(n-1)与达N-2层方法f(n-2)之和。这就找到了我们进行递推的关系式，终止条件即为f(1)=1和f(2)=2;

因此我们可以编程实现计算，实现代码如下：

<script type="text/javascript">
     function f(n) {
       if(n==1 || n==2) {
         return n
       }else {
         return f(n-1)+f(n-2)
       }
     }
     console.log(f(2)) //输出2
     console.log(f(6)) //输出13
</script>