JS递归

一个函数在内部调用自己就叫递归，递归必须加退出条件

    //递归实现阶乘
    function fn(n){
        if(n == 1){
            return 1
        }
        return n * fn(n-1)
    }
    console.log(fn(7));

//斐波那契数列，1、1、2、3、5、8、13、21、34，第三项开始等于前两项之和
    function fb(n){
        if(n <= 2){
            return 1
        }
        return fb(n-1) + fb(n-2)
    }
    console.log(fb(8));

//利用递归获取数据
var data = [{
        id: 1,
        name: '家电',
        goods: [{
            id: 11,
            gname: '冰箱',
            goods: [{
                id: 111,
                gname: '海尔'
            }, {
                id: 112,
                gname: '美的'
            }, ]
        }, {
            id: 12,
            gname: '洗衣机'
        }]
    }, {
        id: 2,
        name: '服饰'
    }];
    function getGoods(array,id){
        var o = {}
        array.forEach(item => {
            if(item.id == id){
                o = item
            }else if(item.goods && item.goods.length > 0){
                o = getGoods(item.goods, id); 
            }
        });
        return o
    }
    console.log(getGoods(data,1));
    console.log(getGoods(data,11)); 
    console.log(getGoods(data,111)); 

可以使用arguments.callee代替函数名

//递归实现阶乘
    function fn(n){
        if(n <= 2){
            return n
        }
        return n * arguments.callee(n-1)
    }
    console.log(fn(7));

写递归分三步：
1、先去确定功能：
实现阶乘

2、找出结束条件，结束条件一般在很小的数去找

if(n <= 2){
  return n
}

3、找出函数的等价关系式：

f(n) = n * fn(n-1)

例子：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1、确立功能：

跳上一个n级的台阶总共有多少种跳法

2、找出结束条件，往小了找

1级：(1)
2级：(1,1) (2)
3级：(1,1,1) (1,2) (2,1)
4级：(1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2)
第四级开始不一样了，前面三级都是返回n种，第四级5种
所以结束条件为：

if(n <= 3){
  return n
}

3、找出函数的等价关系式：

第一次跳1级，所以接下来还有n-1级阶梯，n-1级阶梯有f(n-1)种跳法
第一次跳2级，所以接下来还有n-2级阶梯，n-2级阶梯有f(n-2)种跳法
所以

f(n) = f(n-1) + f(n-2)

function fn(n){
  if(n <= 3){
    return n
  }
  return fn(n-1) + fn(n-2)
}

优化：

function fn(n){
    var arr=[]
    if(n <= 3){
        return n;
    }
    //先判断有没计算过
    if(arr[n]!=null){
        //计算过，直接返回
        return arr[n];
    }else{
        // 没有计算过，递归计算,并且把结果保存到 arr数组里
        arr[n] = fn(n-1) + fn(n-2)
        return arr[n];
    }
}