递归

递归

概念
递归就是函数调用自身，直到达到某种状态。
调用自身的函数就是我们在同一个函数内调用自己。
达到某种状态就是递归有一个临界值使其停下来。
递归与循环
递归和循环可以互相转化。条件是当递归中的参数是固定的时候。
递归的步骤

1. 假设递归函数已经写好
2. 寻找递归关系
3. 把递归关系转化为递归函数
4. 加入临界值

例如求2,4,6,8...的第n项与前n项的和.
分析：

1. 假设f(n),与sum(n)
2. 递归关系
   f(n)=f(n-1)+2
   sum(n)=f(n)+sum(n-1)
3. 加入临界值
   if n=0,ruturn 2
4. 把递归关系转化成递归函数

function fn(n){
    if(n==0) return 2;
    return f(n-1)+2;
}
function sum(n){
    if(n==0) return 2;
    return f(n)+sum(n-1);//返回的是递归关系
}

递归的类型

普通函数中的递归
回文

function fn1(m){
    if(m<=1) return true;
    if(m.charAt(0)!=m.charAt(m.length-1)return false;
    return fn1(m.substr(1,m.length-2);
}//先找其中的一种情况，然后再返回递归关系反复调用。

实现3个‘chirp-chirp-chirp’

function chirp(m){
    if(m==0) return 'chirp';
    if(m>=1) return chirp(m-1)+'-chirp';
}
var a=chirp(2);
console.log(a)//此题注意if条件判断中的等号不是‘=’，而且对于这种字符串的题一般与其下标有关。

++方法中的递归++
可以将上例改为方法：

var obj={
    chirp: function(m){
        if(m==0) return 'chirp';
        if(m>1) return chirp(m-1)+'-chirp';
    }
}

方法递归中引用丢失的问题

var obj={
    chirp: function(n){
       return n>1?obj.chirp(n-1)+'-chirp':'chirp'
    }
}
var ninj={chirp:obj.chirp}
 obj={}//这样操作的话，obj为空，属性被清空后，ninj也会受影响。所以应该把方法中的换成this.这样当ninj用的时候指的就是ninj。

除了可以用this外，还可以给函数起一个名字。

var obj={
    chirp: function sinj(n){
       return n>1?sinj.chirp(n-1)+'-chirp':'chirp'
    }
}
var ninj={chirp:obj.chirp}
obj={}//这样的操作就不会导致递归引用丢失