递归

递归法

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

下面看几个例子：

1.公园里面有200个桃子，每天吃掉一半，扔掉一个烂的，第6天剩余多少桃子

<script type="text/javascript">
    var sl = 200;
    for(var i=0;i<6;i++){
        sl = parseInt(sl/2)-1;
    }
    alert(sl);

</script>

2.公园里有一堆桃子，猴子每天能吃掉一半，扔掉一个烂的，发现第6天的时候剩余1个桃子，问刚开始有多少桃子

注意：这个题目和第一题正好反着

<script type="text/javascript">
    var sl = 1;
    for(var i=0;i<6;i++){
        sl = (sl+1)*2;
    }
    alert(sl);

</script>

在这里我们发现结果为190，第一题中为200，这里的差距差在我们在第一题中

 sl = parseInt(sl/2)-1;
这里去了整数，导致结果出现误差，所这道题的结果也是正确的

3.公园里有一堆桃子，猴子每天能吃掉一半，扔掉一个烂的，发现第6天的时候剩余1个桃子，问刚开始有多少桃子
前面两个题我们都是用了for循环，下面我们用递归的方式解这道题目

解析这道题目：递归
当天的剩余量= (下一天的剩余量+1)*2;
函数明确：给一个天数，返回该天剩余的桃子数量

<script type="text/javascript">
    function shuLiang(ts){
        
        if(ts==6){
            return 1;
        }
        
        return (shuLiang(ts+1)+1)*2;    
    }    
    alert(shuLiang(0));
</script>

我们来一步步的解析递归的解题步骤：

<script type="text/javascript">
    /*function shuLiang(ts){    
        if(ts==6){
            return 1;
        }    
        return (shuLiang(ts+1)+1)*2;    
    }    
    alert(shuLiang(0));*/
    
    //第一次执行
    function shuLiang(0){    //0!=6，所以if(ts==6){return 1;}    这一步就不走了
        return (shuLiang(1)+1)*2;    //因为shuLiang(1)的值未知，所以，这一步卡住，继续下一次执行
    }    
    //第二次执行
    function shuLiang(1){
        return (shuLiang(2)+1)*2;  //同样卡住
    }    
    //第三次执行
    function shuLiang(2){
        return (shuLiang(3)+1)*2;  //同样卡住
    }    
    //第四次执行
    function shuLiang(3){
        return (shuLiang(4)+1)*2;  //同样卡住
    }    
    //第五次执行
    function shuLiang(4){
        return (shuLiang(5)+1)*2;  //同样卡住
    }    
    //第六次执行
    function shuLiang(5){
        return (shuLiang(6)+1)*2;  //同样卡住
    }    
    //第七次执行
    function shuLiang(6){    //上面已经有限制条件，当ts==6的时候，调用函数的返回值为1；
                             //正好第七次执行的时候，6==6.所以，这一次函数有返回值为1，不会再卡住，向上返回了一个值为1
        if(ts==6){
            return 1;
        }    
    }    
    
    //所以，我们在逆向回去
    //第六次执行
    function shuLiang(5){
        return (1+1)*2;    //返回值为4
    }
    //第五次执行
    function shuLiang(4){
        return (4+1)*2;    //返回值为10
    }
    //第四次执行
    function shuLiang(3){
        return (10+1)*2;   //返回值为22
    }
    //第三次执行
    function shuLiang(2){
        return (22+1)*2;   //返回值为46
    }
    //第二次执行
    function shuLiang(1){
        return (46+1)*2;   //返回值为94
    }    
    //第一次执行
    function shuLiang(0){
        return (94+1)*2;   //返回值为190
    }    
    
    
    //最终我们得到的结果为190
</script>

递归就是逐层往里进，有返回值后再逐层往外出

能用递归解决的问题通常具有两个特点：（概括说就是：函数内调用它本身）
1.有退出条件
2.外层需要用到内层算出的结果(也可能是内层需要外层的计算结果，但比较少见)
最难的地方是找出外层利用内层结果的方法，这往往需要在思考问题的过程中发现规律，纸笔是不可缺少的。
另外退出条件需要拿捏准确，这也是一个容易出错的地方。

概括说就是：递归就是某个函数直接或间接地调用了自身，这种调用方式叫做递归调用。说白了，还是函数调用，函数内调用它本身

eg.

function shuLiang(ts){    
        if(ts==6){
            return 1;
        }    
        return (shuLiang(ts+1)+1)*2;    
    }    
    alert(shuLiang(0));


下面再举个例子，文件夹里的文件数量，用递归法

<script type="text/javascript">
    //给一个文件夹，求该文件夹下所有文件的数量
    //函数功能明确：给我一个文件夹，返回该文件夹下文件的数量
    function shuLiang(文件夹路径){
        
        var sum = 0;
        打开文件夹遍历该文件夹下的文件
        if(是文件){
            sum++;
        }else{
            sum = sum + shuLiang(文件夹的路径);
        }
        
        return sum;
    }
</script>