1、 什么是遞歸

在程序中，所謂的遞歸，就是函數自己直接或間接調用自己

1.1 直接調用自己

function f() { 
    console.log( 1 ); 
    f(); 
}  

1.2 間接調用自己

function f1(){ 
    f2(); 
} 
function f2() { 
    f1(); 
}  

就遞歸而言，最重要的是跳出結構，因為只有跳出結構才可以有結果。

1.3 所謂的遞歸就是化歸思想

遞歸的調用，寫遞歸函數，最終還是要轉換為自己這個函數

加入有一個函數f，如果他是遞歸函數的話，也就是說函數體內的問題還是轉化為 f 的形式。

遞歸思想就是將一個問題轉換為一個已解決的問題來實現

例子：1,2,3,4，...,100，累加的結果

• 首先假定遞歸函數已經寫好，假設是foo，即foo(100) 就是求1到100的和
• 尋找遞推關系，就是n與n-1，或n-2之間的關系：foo( n ) == n + foo( n -1 )

var res = foo( 100 ); 
var res = foo( 99 ) + 100;  

• 將遞推結果轉換為遞歸體

function foo ( n ) { 
    return n + foo( n -1 ); 
}  

1. 將求100轉換為求99
2. 將求99轉換為求98
3. ...
4. 將求2轉換為求1
5. 求1結果就是1
6. 即：foo( 1 ) 是1

• 將臨界條件加到遞歸體中

function foo( n ) { 
    return ( n ==1 ) return 1; 
    return n + foo( n -1 ); 
}  

2、 遞歸求值舉例

2.1 等差數列1

數列：求 1, 3, 5, 7, 9, ... 第 n 項的結果與前 n 項和. 序號從 0 開始

求第 n 項的值

• 首先假定遞歸函數已經寫好, 假設是 fn. 那么 第 n 項就是 fn( n )
• 找遞推關系: fn( n ) == f( n - 1 ) + 2
• 遞歸體

function fn( n ) { 
    return fn( n-1 ) + 2; 
}  

• 找臨界條件

         求 n -> n-1

        求 n-1 -> n-2

        ...

        求 1 -> 0

        求 第 0 項, 就是 1

• 加入臨界條件 

function fn( n ) { 
    if ( n == 0 ) return 1; 
    return fn( n-1 ) + 2; 
}  

前N項的和

• 假設已完成, sum( n ) 就是前 n 項和
• 找遞推關系: 前 n 項和 等于 第 n 項 + 前 n-1 項的和
• 得到遞歸體 

function sum( n ) { 
    return fn( n ) + sum( n - 1 ); 
}   

• 找臨界條件

          n == 1 結果為1

• 得到遞歸函數 

function sum( n ) { 
    if ( n == 0 ) return 1; 
    return fn( n ) + sum( n - 1 ); 
}   

2.2 等差數列2

數列：2, 4, 6, 8, 10 第 n 項與 前 n 項和

第n項

function fn( n ) { 
   if ( n == 0 ) return 2;  
   return fn( n-1 ) + 2;  
}  

前n項和 

function sum( n ) {  
   if ( n == 0 ) return 2;  
   return sum( n - 1 ) + fn( n );  
}  

2.3 差分數列

數列: 1, 1, 2, 4, 7, 11, 16, … 求 第 n 項, 求前 n 項和.

求第 n 項，從0開始

• 假設已經得到結果 fn, fn( 10 ) 就是第 10 項
• 找遞推關系

          第 0 項和第 1 項，相差0 => fn( 0 ) + 0 = fn( 1 )

          第 1 項和第 2 項，相差1 => fn( 1 ) + 1 = fn( 2 )

          第 2 項和第 3 項，相差2 => fn( 1 ) + 2 = fn( 2 )

          ...

          第 n-1 項和第 n 項，相差n-1 => fn( n -1 ) + n -1 = fn( n )

• 遞歸體也就清楚了, 臨界條件是 n == 0 => 1 

function fn ( n ){ 
    if( n == 0 ) return 1; 
    return fn( n -1 ) + n - 1; 
}  

如果從 1 開始表示, 那么第 n 項為

• 假設已經得到結果 fn, fn( 10 ) 就是第 10 項
• 找遞推關系

         第 1 項和第 2 項，相差0 => fn( 1 ) + 0 = fn( 2 )

         第 2 項和第 3 項，相差1 => fn( 2 ) + 1 = fn( 3 )

         第 3 項和第 4 項，相差2 => fn( 3 ) + 2 = fn( 4 )

         ...

        第 n-1 項和第第 n 項，相差 n - 1 => fn( n -1 ) + n -2 = fn( n )

• 臨界條件 n == 1 => 1

前n項和

function sum( n ) { 
    if ( n == 1 ) return 1; 
    return sum( n - 1 ) + fn( n );  
} 

 2.4 斐波那契數列

這是最常見，面試***問的知識之一，斐波那契數列為：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

求其第 n 項

遞推關系 fn(n) == fn( n- 1) + fn( n - 2)，于是，遞歸函數為 

function fib ( n ) { 
    if( n ==0 || n == 1 ) return 1; 
    return fib( n -1 ) + fib( n -2 ); 
}  

3、高級遞歸

3.1 階乘

計算階乘是遞歸程序設計的一個經典示例。階乘是一個運算,計算某個數的階乘就是用那個數去乘包括 1 在內的所有比它小的數。例如，factorial(5) 等價于 5*4*3*2*1，而 factorial(3) 等價于 3*2*1。

5! 就是 1 * 2 * 3 * 4 * 5. 0 的階乘是1, 階乘 從 1 開始。

求 n 的階乘

function foo( n ){ 
    if( n == 1 ) return 1; 
    return foo( n -1 ) * n;  
} 
console.log(foo(5));    //120 

 

跟前面的1到100的求和的遞歸函數很相似，只是一個變種

3.2 求冪

求冪就是求 某一個數 幾次方

2*2 2 的 平方, 2 的 2 次方

求 n 的 m 次方

最終要得到一個函數 power( n, m )

n 的 m 次方就是 m 個 n 相乘 即 n 乘以 (m-1) 個 n 相乘

function power( n, m ) { 
    if( m == 1 ) return n; 
    return power( n , m -1 ) * n; 
} 
 
console.log(power(2,3)); //8 

 

4、遞歸深拷貝

如果要實現深拷貝，那么就需要考慮將對象的屬性，與屬性的屬性，....都拷貝過來

4.1 簡單實現

如果要實現：

• 假設已經實現clone( o1,o2 )，將對象 o2 的成員拷貝一份交給 o1
• 簡單的算法，將 o2 的屬性拷貝到 o1 中去

function clone( o1,o2 ){ 
    for( var k in o2 ){ 
        o1[ k ] = o2[ k ];  
    } 
} 

 

• 找遞推關系，或叫化歸為已解決的問題

          假設方法已經實現，問一下，如果o2[ k ] 是對象

          繼續使用這個方法

          因此需要考慮的是o2[ k ] 如果是引用類型，再使用一次clone()函數

          如果o2[ k ] 不是引用類型，那么就直接賦值

function clone( o1, o2 ) { 
        for ( var k in o2 ) { 
            if ( typeof o2[ k ] == 'object' ) { 
                o1[ k ] = {}; 
                clone( o1[ k ] , o2[ k ] ); 
            } else { 
                o1[ k ] = o2[ k ]; 
            } 
        } 
} 
 
var person1 = { 
       name: '張三', 
       children: [ 
            { name: '張一' }, 
            { name: '張二' }, 
            { name: '王三' } 
       ] 
}; 
 
var person2 = {}; 
clone( person2, person1 ); 

 

4.2 復雜實現 clone( o ) -> newObj

function clone( o ) { 
    var temp = {}; 
    for( var k in o ) { 
        if( typeof o[ k ] == 'object' ){ 
             temp[ k ] = clone( o[ k ] ); 
        } else { 
             temp[ k ] = o[ k ]; 
        } 
    } 
    return temp; 
} 
 
var person1 = { 
     name: '張三', 
     children: [ 
        { name: '張一' }, 
        { name: '張二' }, 
        { name: '王三' } 
    ] 
}; 
  
 var person2 = clone(person1); 
// 修改一個看另一個是否也修改 
person2.name = '李四'; 
  
person2.children[ 0 ].name = '王小虎'; 
person2.children[ 1 ].name = '張大虎'; 
person2.children[ 2 ].name = '李長虎'; 

 

4.3 遞歸實現getElementsByClassName方法

有如下DIV結構：

<div> 
    <div>1 
        <div class="c">2</div> 
        <div>3</div> 
    </div> 
    <div class="c">4</div> 
    <div>5 
        <div>6</div> 
        <div class="c">7</div> 
    </div> 
    <div>8</div> 
</div> 

 

1. 如果實現一個方法byClass( node, 'c', list )，表示在某個節點上查找符合 class 屬性為 c 的元素
2. 在當前元素的子元素中查找，如果有符合要求的嗎，存儲早一個數組中
3. 首先遍歷子節點，然后看子節點是否還有子節點，如果沒有直接判斷，如果有再遞歸

function byClass( node, className, list ){ 
    var nodes = node.childNodes; 
    for( var i=0; i<ndoes.length; i++ ){ 
         if( nodes[ i ].className == className ){ 
             list.push( nodes[ i ] ); 
         } 
         if( nodes[ i ].childNodes.length > 0 ){ 
             byClass( nodes[ i ], className, list ); 
         } 
    } 
} 
 
var arr = []; 
byClass( document.body, 'c', arr ); 
console.log(arr);