JS 递归函数

什么是递归函数?

一个通过函数名调用自身的函数

递归函数的注意点

• 一定要有结束条件，否则会导致死循环
• 能用递归函数实现的需求，就一定可以用循环调用函数来解决，只是代码简洁与性能不同而已

---

递归函数的应用场景

1.求阶乘: 求n的阶乘

• 循环写法

        function getMul(n){
            var data = 1;
            for(var i = 1;i<=n;i++){
                data *= i
            }
            return data;
        }
        console.log(getMul(4));//24

• 递归写法
  a.推理版:中间省略

        function getMul(n){
            if(n == 1){
                return 1;
            }else if(n == 2){
                return 2 * getMul(1);
            }else if(n == 3){
                return 3 * getMul(2)
            }
            //*****
            else if(n == n){
                return n * getMul(n-1);
            };
        };
        console.log(getMul(4));//24

b.精简版:三元表达式

        function getMul(n){
            return n == 1 ? 1 : n * getMul(n-1);
        };
        console.log(getMul(4));//24

2.求1-n的累加和

• 循环写法

        function getSum(n){
            var data = 0;
            for(var i = 1;i<=n;i++){
                data += i;
            }
            return  data;
        };
        console.log(getSum(4));//10

• 递归写法
  a.推理版:中间省略

        function getSum(n){
            if(n == 1){
                return 1;
            }else if(n == 2){
                return n + getSum(1);
            }else if(n == 3){
                return n + getSum(2);
            }else if(n == 4){
                return n + getSum(3);
            }
           // ………………
            else if(n == n){
                return n + getSum(n-1)
            }
        };
        console.log(getSum(4));//10

b.精简版:三元表达式

        function getSum(n){
            return n==1 ? 1:n + getSum(n-1);
        };
        console.log(getSum(4));//10

3.求斐波拉契数列

• 斐波拉契数列: 前面两个数字是固定的1,从第三个数字开始，每一个数字都是前面两个数字的和

循环数组写法(性能好)

思路:1.每次计算都是前两个数字之和,其他的数据没有什么用,所以每次只计算两个
arr[n]=arr[n-1]+arr[n-2]

image

        function getData(n) {
            var arr = [1, 1];
            for (var i = 2; i < n; i++) {
                arr[i] = arr[i - 1] + arr[i - 2];
            };
            console.log(arr);//[1,1,2,3,5,8,13,21,34,55]
            return arr[arr.length - 1];
        };
        console.log(getData(10)); //10

递归写法

a.推理版:中间省略

        function getData(n) {
            if(n == 1 || n == 2){
                return 1;
            }else if(n == 3){
                return getData(2) + getData(1);
            }else if(n == 4){
                return getData(3)+getData(2);
            }else if(n == 5){
                return getData(4) + getData(3)
            }
           // …………
            else if(n == n){
                return getData(n-1) + getData(n-2)
            };
        };
        console.log(getData(10)); //10

b.精简版:三元表达式

        function getData(n) {
            return (n == 1 || n == 2)?1 : getData(n-1) + getData(n-2);
        };
        console.log(getData(10)); //10

4.遍历DOM树:获取所有的后代元素

a.需求:获得div中所有的后代元素
b.思路:获取father的子代元素。 继续检查该元素是否有子代元素，
如果有则继续循环获取子代，依次类推，形成递归调用

            <div id="father">
        <div>
            <span>1</span>>
        </div>
        <p>
            <span>11</span>
            <span>22</span>
        </p>
        <a href="#">boJack</a>
        <div>
            <div>
                <b>Todd</b>
            </div>
        </div>
    </div>
    <script>
        var father = document.getElementById('father');
        var list = []; //声明空数组存储所有的后代元素
        function getHouDai(ele) {
            for (var i = 0; i < ele.children.length; i++) {
                list.push(ele.children[i]);
                getHouDai(ele.children[i]);
            };
        };
        getHouDai(father);
        console.log(list);//[span,p,span,span,a,div,div,b]

// 遍历整颗DOM树
        getHouDai(document);
        console.log(list);
    </script>

经典面试题以及推荐用法

a.写出该题打印的值

        var res = (function(n){ return n==1?1:n*arguments.callee(n-1)})(6);
        console.log('res' + res);//res720

考察的知识点:argument.callee

• argument.callee是一个指向正在执行的函数的指针,使用它来代替函数名,可以确保无论怎样调用函数都不会出问题

        function res(n) {
            return n ==1 ? 1 : n * res(n - 1);
        };
        var  data = res;
        res = null;
        console.log(data(4));
        //res is not a function

由于res变量设置为Null,结果指向原始函数的引用只剩下一个,res已经不是函数,而调用data()会执行res,所以会报错;而使用arguments.callee可以解决这个问题

        function res(n) {
            return n ==1 ? 1 : n * arguments.callee(n - 1);
        };
        var  data = res;
        res = null;
        console.log(data(4));//24

推荐用法

• 严格模式:使用arguments.callee会报错,不过我们可以通过命名函数表达式来达到相同的效果
  以下代码创建了一个f()的命名函数表达式,赋值给res变量,即使把函数赋值给另一个变量,函数的名字依然有效,递归能正常完成,这种方式在严格模式和非严格模式都能运行

        var res=(function f(n) {
            return n ==1 ? 1 : n * f(n - 1);
        });
        console.log(res(4));//24