Detailed explanation of javascript recursive functions (with examples)

This article brings you a detailed explanation of JavaScript recursive functions (with examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

I have seen recursive functions many times, but I never felt that I fully understood them. This time I had time to read "Advanced JavaScript Programming" and calmed down to read it again. Recursion, I feel like I finally understand a little bit, summarize my stupid way to solve this kind of problem, haha

Recursive function is to pass the name of a functionCall your own function
This is the definition in the book, but it is actually the same. I will be confused when encountering similar interview questions

Let’s first look at a case in the book

function factorial(num){ 
    if (num <= 1){ 
         return 1; 
    } else { 
        return num * factorial(num-1); 
    } 
}

A classic factorial recursion, it is easy to understand this code, but if you are asked to use recursion to write a factorial, some people will be bored.
My idea is

Step 1: Find the starting point

    factorial(1) =  1  = 1   //要思考这个递归的起点在哪里,就像阶乘就是1  而累加的话就是0
    factorial(2) =  2 * 1  =2  //接着我们试着多写等式然后找出规律
    factorial(3) =  3 *  2  *  1 = 6
    factorial(4) =  4 *  3  *  2  * 1  = 24

Step 2: Function to replace numbers

    // 我们试着将等式右边的实际变量用左边的函数替换
    factorial(1) =  1  = 1
    factorial(2) =  2 * factorial(1) = 2    
    factorial(3) =  3 * factorial(2) = 6    
    factorial(4) =  4 * factorial(3) = 24

Step 3: Find patterns

    factorial(4) =  4 * factorial(3) = 24 
    //以的阶乘为例  4! =  4 *  3!(3的阶乘)
    //而3!其实就是这个函数本身,ta会继续调用递归函数直至调用到factorial(1)
    
    //把4替换成参数
    factorial(n) =  n * factorial(n - 1)

Step 4: Convert to recursive function

    再看下步骤2
        情况1:起点
        factorial(1) =  1  = 1
        情况2:费起点
        factorial(2) =  2 * factorial(1) = 2    
        factorial(3) =  3 * factorial(2) = 6    
        factorial(4) =  4 * factorial(3) = 24  
     
    所以方法内应该需要两种情况
        function  factorial(n){
            if(n>=1){
                 return  n *  factorial(n - 1)
            }else{
                return 1   //起点其实就是递归方法返回的起始值
            }
        }

If there is still no way To understand this recursive function, we can split all recursions into anonymous functions

    //我们计算一个4阶乘
    fun(4){
        return  4 *  fun(3)
    }
    
    fun(3){
        return 3 *  fun(2)
    }

    fun(2){
        return  2 *  fun(1)
    }
    
    fun(1){
        return 1 
    }

   你运行fun(4)的时候,一层一层想内访问,访问到fun(1)时候,再讲所有的已知变量计算出结果
    fun(4)=>fun(3)=>fun(2)=>fun(1)=>fun(2)=>fun(3)=>fun(4)

    return  4 *  3 *  2 * 1

Then use my stupid method to try other examples, haha, I should be able to handle most of the interview questions

Chestnut 1:

    //计算1-10之间的和

    //fun(0) = 0;            //0
    //fun(1) = 1;            //1
    //fun(2) = 2 +  fun(1)   //3
    //fun(3) = 3 +  fun(2)   //6
    //fun(4) = 4 +  fun(3)   //10

    
    function fun(num){
        if(num > 1){
            return num + fun(num-1)
        }else{
            return 1
        }
    
    }
    
    
    fun(10)   //55

Chestnut 2:

    
    //一共有n格，每步可以走1格或者2格，问一共有多少走法。 
    // fn(1) =  1    //一个格子的时候只能走一步,所有只有一种走法
    // fn(2) =  2    //两个格子的时候,可以一次走1个两步,也可以走2个一步,所以是2种走法,后面就要拿个草稿纸算下了
    // fn(3) =  3    // fn(2) + fn(1)
    // fn(4) =  5    // fn(3) + fn(2)
    // fn(5) =  8    // fn(4) + fn(3)   //规律 :fn(n) =  fn(n-1) +  fn(n-2)  个人认为所有能做递归函数的,都是有规律可寻的.即便不是很理解其中的原理,但是通过代入数字,也是可以很快发现的这些相同之处,概括成函数的.
    
    function  fun(num){
        if(num == 1){
            return 1
        }else if(num == 2){
            return 2
        }else{
            return  fun(num-1) +  fun(num-2)
        }
    }
    
    fun(5)  // 8

I probably only know so much about recursive functions. If you have any recursive interview questions, you can leave a message to discuss them together, haha

The above is the detailed content of Detailed explanation of javascript recursive functions (with examples). For more information, please follow other related articles on the PHP Chinese website!