進階JavaScript之玩轉(zhuǎn)遞歸與數(shù)列

作者：dunizb 2016-09-06 20:46:53

在程序中，所謂的遞歸，就是函數(shù)自己直接或間接調(diào)用自己。就遞歸而言，最重要的是跳出結(jié)構(gòu)，因為只有跳出結(jié)構(gòu)才可以有結(jié)果。

1、什么是遞歸

在程序中，所謂的遞歸，就是函數(shù)自己直接或間接調(diào)用自己

1.1 直接調(diào)用自己

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

1.2 間接調(diào)用自己

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

就遞歸而言，最重要的是跳出結(jié)構(gòu)，因為只有跳出結(jié)構(gòu)才可以有結(jié)果。

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

遞歸的調(diào)用，寫遞歸函數(shù)，最終還是要轉(zhuǎn)換為自己這個函數(shù)

加入有一個函數(shù)f，如果他是遞歸函數(shù)的話，也就是說函數(shù)體內(nèi)的問題還是轉(zhuǎn)化為 f 的形式。

遞歸思想就是將一個問題轉(zhuǎn)換為一個已解決的問題來實現(xiàn)

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

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

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

將遞推結(jié)果轉(zhuǎn)換為遞歸體

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

將求100轉(zhuǎn)換為求99
將求99轉(zhuǎn)換為求98
...
將求2轉(zhuǎn)換為求1
求1結(jié)果就是1
即：foo( 1 ) 是1

將臨界條件加到遞歸體中

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

2、遞歸求值舉例

2.1 等差數(shù)列1

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

求第 n 項的值

首先假定遞歸函數(shù)已經(jīng)寫好, 假設(shè)是 fn. 那么第 n 項就是 fn( n )
找遞推關(guā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項的和

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

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

找臨界條件

n == 1 結(jié)果為1

得到遞歸函數(shù)

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

2.2 等差數(shù)列2

數(shù)列：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 差分?jǐn)?shù)列

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

求第 n 項，從0開始

假設(shè)已經(jīng)得到結(jié)果 fn, fn( 10 ) 就是第 10 項
找遞推關(guān)系

第 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 項為

假設(shè)已經(jīng)得到結(jié)果 fn, fn( 10 ) 就是第 10 項
找遞推關(guān)系

第 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 斐波那契數(shù)列

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

求其第 n 項

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

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

3、高級遞歸

3.1 階乘

計算階乘是遞歸程序設(shè)計的一個經(jīng)典示例。階乘是一個運算,計算某個數(shù)的階乘就是用那個數(shù)去乘包括 1 在內(nèi)的所有比它小的數(shù)。例如，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的求和的遞歸函數(shù)很相似，只是一個變種

3.2 求冪

求冪就是求某一個數(shù) 幾次方

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

求 n 的 m 次方

最終要得到一個函數(shù) 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、遞歸深拷貝

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

4.1 簡單實現(xiàn)

如果要實現(xiàn)：

假設(shè)已經(jīng)實現(xiàn)clone( o1,o2 )，將對象 o2 的成員拷貝一份交給 o1
簡單的算法，將 o2 的屬性拷貝到 o1 中去

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

找遞推關(guān)系，或叫化歸為已解決的問題

假設(shè)方法已經(jīng)實現(xiàn)，問一下，如果o2[ k ] 是對象

繼續(xù)使用這個方法

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

如果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 復(fù)雜實現(xiàn) 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 遞歸實現(xiàn)getElementsByClassName方法

有如下DIV結(jié)構(gòu)：

<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>

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

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);

責(zé)任編輯：龐桂玉來源： segmentfault