App下載

遞歸函數(shù):遞歸到底是什么? JavaScript代碼展示

重度健忘癥患者 2021-08-30 11:46:24 瀏覽數(shù) (2681)
反饋

遞歸是一種通過迭代解決問題的方法。換句話說,遞歸函數(shù)是一個(gè)無限重復(fù)調(diào)用自身的函數(shù)(或直到某事停止它)。

關(guān)于遞歸函數(shù)的重要知識

每當(dāng)你選擇使用遞歸函數(shù)時(shí),請記住這兩個(gè)基本信息。

信息 1:遞歸不是 IIFE

遞歸函數(shù)不同于立即調(diào)用函數(shù)表達(dá)式(IIFE)。

IIFE 會(huì)自動(dòng)調(diào)用一次自身。

但是,遞歸函數(shù)會(huì)在無限時(shí)間內(nèi)自動(dòng)重復(fù)調(diào)用自己,或者直到某些東西停止重新調(diào)用為止。

信息 2:遞歸函數(shù)需要一個(gè)基本情況

為停止遞歸函數(shù)的重新調(diào)用而編寫的代碼稱為基本情況。

在創(chuàng)建遞歸函數(shù)時(shí)定義基本情況總是很重要的——這樣函數(shù)就不會(huì)無休止地運(yùn)行,從而使瀏覽器崩潰。

遞歸函數(shù)的例子

下面是一個(gè)JavaScript代碼,它返回通過函數(shù)的遞歸調(diào)用返回的所有值串聯(lián)countDown()

// Create a recursive function:
function countDown(num) {
   // Define the base case of this recursive function:
   if (num < 0) {
      return "Recursion Stopped!";
   }

   // Define the recursive case:
   return num + ", " + countDown(num - 1);
}

// Invoke the countDown() recursive function:
countDown(2);

// The invocation above will return:
"2, 1, 0, Recursion Stopped!"

筆記

在上面的遞歸算法中,countDown(num - 1)代碼使整個(gè)函數(shù)成為遞歸,因?yàn)槭?/font>代碼使countDown()recall本身重復(fù)。

看看幕后的事件

當(dāng)我們調(diào)用countDown函數(shù)并傳入值2(即countDown(2))時(shí),算法開始運(yùn)行如下:

第 1 步:檢查是否2小于0

計(jì)算機(jī)檢查了2我們傳遞給函數(shù)num參數(shù)的countDown值是否小于0。

由于2不小于0,計(jì)算機(jī)沒有執(zhí)行if語句的代碼。相反,它跳到if語句之后的下一個(gè)代碼——遞歸代碼。

第二步:執(zhí)行return語句

跳過if語句后,計(jì)算機(jī)執(zhí)行return num + " " + countDown(num - 1)代碼——但num用參數(shù)的值(即2替換參數(shù),如下所示:

return num + ", " + countDown(num - 1);
return 2 + ", " + countDown(2 - 1);
return 2 + ", " + countDown(1);

第 3 步:僅執(zhí)行遞歸語句

在上面第 2 步的代碼中,請注意該return命令無法返回任何值,因?yàn)樵?/font>return語句包含countDown(1)調(diào)用該countDown函數(shù)的遞歸代碼 ( ) 。

因此,在保留return語句的其他部分(即2 + ", " +)的同時(shí),計(jì)算機(jī)將只執(zhí)行遞歸代碼(countDown(1))。

換句話說,countDown(1)代碼將countDown在傳入 value 時(shí)自動(dòng)調(diào)用該函數(shù)1然后,算法將通過檢查是否1小于重新開始運(yùn)行0。

由于1不小于0,計(jì)算機(jī)跳到遞歸代碼,如下所示:

return 2 + ", " + num + ", " + countDown(num - 1);
return 2 + ", " + 1 + ", " + countDown(1 - 1);
return 2 + ", " + 1 + ", " + countDown(0);

第 4 步:僅調(diào)用遞歸代碼

再次注意,該return命令(在第 3 步中)不能返回任何值,因?yàn)樵?/font>return語句包含countDown(0)調(diào)用該countDown函數(shù)的遞歸代碼 ( ) 。

因此,在保留return語句的其他部分(即2 + ", " + 1 + ", " +)的同時(shí),計(jì)算機(jī)將只執(zhí)行遞歸代碼(countDown(0))。因此,countDown(0)代碼將countDown在傳入 value 時(shí)自動(dòng)調(diào)用該函數(shù)0

然后,該函數(shù)將通過檢查是否0小于重新開始運(yùn)行0。

由于0不小于0,計(jì)算機(jī)跳到遞歸代碼,如下所示:

return 2 + ", " + 1 + ", " + num + ", " + countDown(num - 1);
return 2 + ", " + 1 + ", " + 0 + ", " + countDown(0 - 1);
return 2 + ", " + 1 + ", " + 0 + ", " + countDown(-1);

第五步:只執(zhí)行遞歸代碼

再說一次,該return命令(在第 4 步中)不能返回任何值,因?yàn)樵?/font>return語句包含一個(gè)遞歸代碼 ( countDown(-1)) 來調(diào)用該countDown函數(shù)。

因此,在保留return語句的其他部分(即2 + ", " + 1 + ", " + 0 + ", " +)的同時(shí),計(jì)算機(jī)將只執(zhí)行遞歸代碼(countDown(-1))。因此,countDown(-1)代碼將countDown在傳入 value 時(shí)自動(dòng)調(diào)用該函數(shù)-1。

然后,該函數(shù)將通過檢查是否-1小于重新開始運(yùn)行0。

此時(shí),-1小于0。因此,計(jì)算機(jī)將if通過返回值來執(zhí)行語句的代碼,“Recursion Stopped!”如下所示:

return 2 + ", " + 1 + ", " + 0 + ", " + "Recursion Stopped!";

最后,該return語句現(xiàn)在具有可以有效連接和返回的值。因此,從的返回值countDown將是:

"2, 1, 0, Recursion Stopped!"

總結(jié)

在本文中,我們了解到遞歸函數(shù)是一種重復(fù)調(diào)用自身直到某事停止調(diào)用的函數(shù)。

謝謝閱讀!

0 人點(diǎn)贊