JavaScript遞歸與數列的知識點講解

本篇內容介紹了“JavaScript遞歸與數列的知識點講解”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

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

“JavaScript遞歸與數列的知識點講解”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！