JavaScriptでの再帰関数および再帰的コピー

さいきかんすう
再帰関数:関数内部の直接または間接的な呼び出し自体
再帰的な要件:

自己呼び出し自己(直接または間接)

終了条件(出口)

//    
function fn() {
    console.log(123);
    fn();//        ,    ,      ,    123
}
fn(); //  fn  

//    
var count = 0; //   fn       

function fn(){
    console.log(123);
    
    count++; //       +1           
    
    // if     ，       
    if(count < 5){
        fn();
    }
}
fn();//  fn  

再帰関数は主に であり,複雑な問題を単純化し,主に数学におけるいくつかの問題の解決に用いられることが多い.

解決すべき問題を、解決した問題にまとめる.

は、関数をいつ終了するか、すなわち再帰停止(必ず既知の条件がある)

を考慮しなければならない.
いくつか例を挙げてみましょう
1.1-100の間と

// sum            
//   n 1-n    
function sum(n){

    // 2.        
    if(n === 1){
        return 1; // return         
    }
    
    // 1.      （  ，       ）
    return sum(n - 1) + n;
}

console.log(sum(100)); //5050
// 1-100       

//             sum(100)
// sum(100) ==> sum(99) + 100; // sum(99) ==> 1-99        + 100
// sum(99) ==> sum(98) + 99;
// sum(98) ==> sum(97) + 98;
// ...
// sum(3) ==> sum(2) + 3;
// sum(2) ==> sum(1) + 2;
// sum(1) ==> 1

//           
//  sun(n) ==> sum(n - 1) + n;

2.10の階乗を求める:

//   n 1-n     
function product(n) {
    // 2.        
    if (n === 1) {
        return 1 // return         
    }
    // 1.      （  ，       ）
    return product(n - 1) * n
}
console.log(product(10));//362880
//  10   

//    product(20)
// product(10) ==> product(9) * 10
// product(9) ==> product(8) * 9
// product(8) ==> product(7) * 8
// ...
// product(2) ==> product(1) * 2
// product(1) ==> 1

//     
// product(n - 1) * n

3.フィボナッチ数列を求める:

//       ： 1 1 2 3 5 8 13 21 34 55  89  144(      )
function fib(n) {

    // 2.        
    if (n === 1 || n === 2) {
        return 1;
    }
    
    // 1.         
    return fib(n - 1) + fib(n - 2);
}

console.log(fib(6));// 8

//     
// fib(40) ==> fib(39) + fib(38);  
// fib(39) ==> fib(38) + fib(37);
// ...
// fib(4) ==> fib(3) + fib(2);
// fib(3) ==> fib(2) + fib(1);
// fib(2) ==> 1
// fib(1) ==> 1
// fib(n) ==> fib(n - 1) + fib(n - 2);

//   :+       ,        

最適化コードは次のとおりです.

//     
var cache = {
/*
    1: 1,
    2: 1,
    3: 2,
    4: 3, 
    5: 5,
    6: 8,
    7: 13
*/
};

function fib(n){
    

    // 2.        
    if(n === 1 || n === 2){
        return 1;
    }
    // 1.         
    //              
    if(cache[n]){
        // if   ，           
        return cache[n];
        //           
        
        // 1.      
        // 2.          
        return cache[n] = fib(n - 1) + fib(n - 2) 
    }
}
console.log(fib(6))//8

//            
function deepClone(source) {
    let target
    if (typeof source === 'object' && source !== null) {
        //              
        target = Array.isArray(source) ? [] : {}
        //        
        for (let key in source) {
            //         
            if (source.hasOwnProperty(key)) {
                if (typeof key === 'object' && key !== null) 
                    target[key] = deepClone(source[key])
                else
                    //   key   ,   key   
                    target[key] = source[key]
            }
        }
    } else {
        //       
        target = source
    }
    return target
}