JavaScript遞歸與數(shù)列的知識(shí)點(diǎn)講解

本篇內(nèi)容介紹了“JavaScript遞歸與數(shù)列的知識(shí)點(diǎn)講解”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

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)，因?yàn)橹挥刑鼋Y(jié)構(gòu)才可以有結(jié)果。

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

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

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

遞歸思想就是將一個(gè)問(wèn)題轉(zhuǎn)換為一個(gè)已解決的問(wèn)題來(lái)實(shí)現(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 ); }

1. 將求100轉(zhuǎn)換為求99

2. 將求99轉(zhuǎn)換為求98

3. ...

4. 將求2轉(zhuǎn)換為求1

5. 求1結(jié)果就是1

6. 即：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 項(xiàng)的結(jié)果與前 n 項(xiàng)和. 序號(hào)從 0 開始

求第 n 項(xiàng)的值

• 首先假定遞歸函數(shù)已經(jīng)寫好, 假設(shè)是 fn. 那么 第 n 項(xiàng)就是 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 項(xiàng), 就是 1

• 加入臨界條件 

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

前N項(xiàng)的和

• 假設(shè)已完成, sum( n ) 就是前 n 項(xiàng)和

• 找遞推關(guān)系: 前 n 項(xiàng)和 等于 第 n 項(xiàng) + 前 n-1 項(xiàng)的和

• 得到遞歸體 

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 項(xiàng)與 前 n 項(xiàng)和

第n項(xiàng)

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

前n項(xiàng)和

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 項(xiàng), 求前 n 項(xiàng)和.

求第 n 項(xiàng)，從0開始

• 假設(shè)已經(jīng)得到結(jié)果 fn, fn( 10 ) 就是第 10 項(xiàng)

• 找遞推關(guān)系

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

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

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

        ...

        第 n-1 項(xiàng)和第 n 項(xiàng)，相差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 項(xiàng)為

• 假設(shè)已經(jīng)得到結(jié)果 fn, fn( 10 ) 就是第 10 項(xiàng)

• 找遞推關(guān)系

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

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

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

       ...

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

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

前n項(xiàng)和

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

2.4 斐波那契數(shù)列

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

求其第 n 項(xiàng)

遞推關(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、高級(jí)遞歸

3.1 階乘

計(jì)算階乘是遞歸程序設(shè)計(jì)的一個(gè)經(jīng)典示例。階乘是一個(gè)運(yùn)算,計(jì)算某個(gè)數(shù)的階乘就是用那個(gè)數(shù)去乘包括 1 在內(nèi)的所有比它小的數(shù)。例如，factorial(5)  等價(jià)于 5*4*3*2*1，而 factorial(3) 等價(jià)于 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ù)很相似，只是一個(gè)變種

3.2 求冪

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

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

求 n 的 m 次方

最終要得到一個(gè)函數(shù) power( n, m )

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

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

4、遞歸深拷貝

如果要實(shí)現(xiàn)深拷貝，那么就需要考慮將對(duì)象的屬性，與屬性的屬性，....都拷貝過(guò)來(lái)

4.1 簡(jiǎn)單實(shí)現(xiàn)

如果要實(shí)現(xiàn)：

• 假設(shè)已經(jīng)實(shí)現(xiàn)clone( o1,o2 )，將對(duì)象 o2 的成員拷貝一份交給 o1

• 簡(jiǎn)單的算法，將 o2 的屬性拷貝到 o1 中去

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

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

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

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

        因此需要考慮的是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ù)雜實(shí)現(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); // 修改一個(gè)看另一個(gè)是否也修改 person2.name = '李四';   person2.children[ 0 ].name = '王小虎'; person2.children[ 1 ].name = '張大虎'; person2.children[ 2 ].name = '李長(zhǎng)虎';

4.3 遞歸實(shí)現(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>

1. 如果實(shí)現(xiàn)一個(gè)方法byClass( node, 'c', list )，表示在某個(gè)節(jié)點(diǎn)上查找符合 class 屬性為 c 的元素

2. 在當(dāng)前元素的子元素中查找，如果有符合要求的嗎，存儲(chǔ)早一個(gè)數(shù)組中

3. 首先遍歷子節(jié)點(diǎn)，然后看子節(jié)點(diǎn)是否還有子節(jié)點(diǎn)，如果沒(méi)有直接判斷，如果有再遞歸

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遞歸與數(shù)列的知識(shí)點(diǎn)講解”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！