遞歸javascript

In this article I will touch on a few important ideas to help you understand Recursion in JavaScript. I’m not going to give a full definition here, but you can take a look at what Wikipedia has to say.

在本文中，我將介紹一些重要的想法，以幫助您了解JavaScript中的遞歸。 我不會(huì)在這里給出完整的定義，但是您可以看看Wikipedia怎么說 。

Let’s agree for the purpose of this article that we are trying to solve a problem by using a function that will then call itself.

出于本文的目的，讓我們同意我們正在嘗試通過使用一個(gè)將自身調(diào)用的函數(shù)來解決問題。

挑戰(zhàn) (The Challenge)

At the end of the Javascript Algorithms and Data Structures?—?Basic Javascript section on freeCodeCamp, you run into an interesting problem: ‘Use Recursion to Create a Range of Numbers’, where the instructions are as follows:

在freeCodeCamp上的Javascript算法和數(shù)據(jù)結(jié)構(gòu)— Basic Javascript部分的最后 ，您遇到了一個(gè)有趣的問題：“使用遞歸創(chuàng)建數(shù)字范圍”，其說明如下：

We have defined a function named rangeOfNumbers with two parameters. The function should return an array of integers which begins with a number represented by the startNum parameter and ends with a number represented by the endNum parameter. The starting number will always be less than or equal to the ending number. Your function must use recursion by calling itself and not use loops of any kind. It should also work for cases where both startNum and endNum are the same.我們定義了一個(gè)帶有兩個(gè)參數(shù)的名為rangeOfNumbers的函數(shù)。 該函數(shù)應(yīng)返回一個(gè)整數(shù)數(shù)組，該數(shù)組以startNum參數(shù)表示的數(shù)字開頭，以endNum參數(shù)表示的數(shù)字結(jié)尾。 起始編號(hào)將始終小于或等于終止編號(hào)。 您的函數(shù)必須通過調(diào)用自身來使用遞歸，而不能使用任何形式的循環(huán)。 它還適用于startNum和endNum相同的情況。

Sounds simple enough – if you were to run rangeOfNumbers(1, 5) it should return [1, 2, 3, 4, 5].

聽起來很簡(jiǎn)單–如果要運(yùn)行rangeOfNumbers(1，5)，它應(yīng)該返回[1、2、3、4、5]。

If you’re like me, you can sort of intuit the answer based on the previous example in this section. But it might still be a bit unclear how this all works.

如果您像我一樣，可以根據(jù)本節(jié)中的上一個(gè)示例來直觀地回答問題。 但這可能還不清楚。

Spoiler alert: you'll find an answer immediately below. But this isn’t much of a spoiler since the answer is easy enough to find on the internet.

劇透警報(bào)：您會(huì)在下面立即找到答案。 但這并不會(huì)破壞太多，因?yàn)榇鸢负苋菀自诨ヂ?lián)網(wǎng)上找到。

我的解決方案 (My Solution)

It’s very probable that you can read through the code and understand that when it gets down to its base case it will return whatever the startNum is into the array. Then it will keep pushing the other values onto that array until it’s done with all of its recursive calls.

您很可能可以通讀代碼并了解其基本情況 ，它將返回?cái)?shù)組中的startNum。 然后它將繼續(xù)將其他值推入該數(shù)組，直到完成所有遞歸調(diào)用為止。

function rangeOfNumbers(startNum, endNum) {if (startNum === endNum) {return [startNum];} else { const numbers = rangeOfNumbers(startNum, endNum - 1);numbers.push(endNum);return numbers;} }

What I found to be tricky was understanding exactly how the call stack was working and how my values were being returned.

我發(fā)現(xiàn)棘手的是確切地了解調(diào)用堆棧如何工作以及如何返回我的值。

So let's break down how this function will return its final value.

因此，讓我們分解一下此函數(shù)將如何返回其最終值。

調(diào)用堆棧 (The Call Stack)

The first thing to understand is how the call stack works. I will refer you to Mozilla Developer Network's explanation:

首先要了解的是調(diào)用堆棧如何工作。 我將向您介紹Mozilla開發(fā)人員網(wǎng)絡(luò)的解釋 ：

When a script calls a function, the interpreter adds it to the call stack and then starts carrying out the function.

當(dāng)腳本調(diào)用函數(shù)時(shí)，解釋器將其添加到調(diào)用堆棧中，然后開始執(zhí)行該函數(shù)。

When a script calls a function, the interpreter adds it to the call stack and then starts carrying out the function.

當(dāng)腳本調(diào)用函數(shù)時(shí)，解釋器將其添加到調(diào)用堆棧中，然后開始執(zhí)行該函數(shù)。

Any functions that are called by that function are added to the call stack further up, and run where their calls are reached.

該函數(shù)調(diào)用的所有函數(shù)都會(huì)進(jìn)一步添加到調(diào)用堆棧中，并在到達(dá)其調(diào)用的位置運(yùn)行。

Any functions that are called by that function are added to the call stack further up, and run where their calls are reached.

該函數(shù)調(diào)用的所有函數(shù)都會(huì)進(jìn)一步添加到調(diào)用堆棧中，并在到達(dá)其調(diào)用的位置運(yùn)行。

Using this explanation, let’s run the code above using rangeOfNumbers(1,5).

使用此說明，讓我們使用rangeOfNumbers(1,5)運(yùn)行上面的代碼。

First the rangeOfNumbers?—?Execution Context is created and executed with the following values:

首先，使用以下值創(chuàng)建并執(zhí)行rangeOfNumbers —執(zhí)行上下文：

So we have added an unresolved rangeOfNumbers(1,5) function call to our stack. Then we move on to create the execution for rangeOfNumbers(1,4), and so on and so forth, adding each one of these calls to our stack until we will finally resolve a function call. Then the interpreter will take that function off the stack and move on to the next one.

因此，我們向堆棧中添加了一個(gè)未解決的rangeOfNumbers(1,5)函數(shù)調(diào)用。 然后，我們繼續(xù)為rangeOfNumbers(1,4)創(chuàng)建執(zhí)行程序， 依此類推 ， 依次類推，將這些調(diào)用中的每一個(gè)添加到堆棧中，直到最終解決函數(shù)調(diào)用為止。 然后，解釋器將從堆棧中刪除該函數(shù)，然后移至下一個(gè)函數(shù)。

檢查我們的通話堆棧 (Examining Our Call Stack)

So our stack will end up looking like this:

因此，我們的堆棧最終將如下所示：

rangeOfNumbers(1,1) rangeOfNumbers(1,2) rangeOfNumbers(1,3) rangeOfNumbers(1,4) rangeOfNumbers(1,5)

rangeOfNumbers(1,1) will be the last one in our stack because, finally, this call will RETURN a value allowing us to move on to our next function in the stack.

rangeOfNumbers(1,1)將是堆棧中的最后一個(gè)，因?yàn)樽詈?#xff0c;此調(diào)用將返回一個(gè)值，使我們可以繼續(xù)執(zhí)行堆棧中的下一個(gè)函數(shù)。

rangeOfNumbers(1,1) return value is [1], as we had assumed it would be since it is our base case. Now we pop rangeOfNumbers(1,1) off our stack, and go back to where rangeOfNumbers(1,2) left off…

rangeOfNumbers(1,1)的返回值是[1]，正如我們已經(jīng)假定的那樣，因?yàn)樗俏覀兊幕厩闆r。 現(xiàn)在，我們從堆棧中彈出rangeOfNumbers(1,1) ，然后返回到距離rangeOfNumbers(1,2)不遠(yuǎn)的地方…

var numbers = rangeOfNumbers(1,2) // returns an array of [1]

Numbers is no longer undefined and the next step is to push the endNum, which is 2, into the numbers array. This gives us [1,2] in numbers, and now we return the value.

Numbers不再是未定義的 ，下一步是將為 2的endNum推入numbers數(shù)組。 這樣就給了我們[1,2]個(gè)數(shù)字，現(xiàn)在我們返回了值。

numbers.push(endNum) //numbers now holds an array of [1,2] return numbers; // ends our function and returns [1,2]

分解棘手的部分 (Breaking Down The Tricky Part)

So we pop off rangeOfNumbers(1,2) which had a return value of [1,2]. Let’s resume with the next call in our stack rangeOfNumbers(1,3). Numbers is currently [1,2] because that is the return value of rangeOfNumbers(1,2). This is what we had plugged in when we called rangeOfNumbers(1,3) because, again, the 3 is subtracted by 1, that is rangeOfNumbers(1,2), which as we said returns [1,2].

因此，我們彈出rangeOfNumbers(1,2) ，其返回值為[1,2]。 讓我們從堆棧rangeOfNumbers(1,3)中的下一個(gè)調(diào)用繼續(xù)。 Numbers當(dāng)前為[1,2]，因?yàn)槟鞘莚angeOfNumbers(1,2)的返回值。 這就是我們?cè)谡{(diào)用rangeOfNumbers(1,3)時(shí)插入的內(nèi)容，因?yàn)樵俅螌?減去1，即rangeOfNumbers(1,2) ，正如我們所說的返回[1,2]。

Got it? Great! If you don’t get it, reread this paragraph, because this is the trickiest part to understand.

得到它了？ 大！ 如果不理解，請(qǐng)重新閱讀本段，因?yàn)檫@是最難理解的部分。

If you’re up to speed let’s continue. If that part above clicked the rest should feel pretty easy.

如果您要加快速度，那就繼續(xù)吧。 如果單擊上方的那部分，其余部分應(yīng)該會(huì)很容易。

Back to rangeOfNumbers(1,3): the numbers array is currently [1,2], so we push the endNum which is 3. Now we have [1,2,3] and we return this value again. We remove rangeOfNumbers(1,3) from our stack which returned the value [1,2,3].

返回rangeOfNumbers(1,3) ：numbers數(shù)組當(dāng)前為[1,2]，因此我們將endNum推為3。現(xiàn)在我們有了[1,2,3]，然后再次返回該值。 我們從返回值[1,2,3]的堆棧中刪除rangeOfNumbers(1,3) 。

How did we get rangeOfNumbers(1,3)? That’s right, from when we called rangeOfNumbers(1,4) and endNumb -1, that is → 3, and we know that rangeOfNumbers(1,3) gives us the return value of [1,2,3] which is exactly what we have in our array.

我們?nèi)绾潍@得rangeOfNumbers(1,3)？ 沒錯(cuò)，從我們調(diào)用rangeOfNumbers(1,4)和endNumb -1開始，即→3，并且我們知道rangeOfNumbers(1,3)為我們提供了[1,2,3]的返回值我們有我們的陣列。

Now we push the endNum (also known as 4) onto the numbers array, giving us [1,2,3,4] and we return this value. Let’s again remove this function call from the stack since it gave us what we wanted.

現(xiàn)在我們將endNum(也稱為4)壓入數(shù)字?jǐn)?shù)組，得到[1,2,3,4]并返回此值。 讓我們?cè)俅螐亩褩Ｖ袆h除此函數(shù)調(diào)用，因?yàn)樗鼭M足了我們的需求。

匯集全部 (Bringing it all together )

Now for the call that started it all: rangeOfNumbers(1,5). The first step we do is determine what value we have in numbers. When put in rangeOfNumbers(1,4) we get, as we said before, [1,2,3,4]. So we can now push our endNum 5 into the array and get [1,2,3,4,5] which we will return, and our stack is now empty with our last call.

現(xiàn)在開始所有的調(diào)用： rangeOfNumbers(1,5) 。 我們要做的第一步是確定數(shù)字所具有的價(jià)值。 如前所述，將rangeOfNumbers(1,4)放入[1,2,3,4]。 因此，我們現(xiàn)在可以將endNum 5推入數(shù)組并獲取[1,2,3,4,5]，我們將返回它，并且我們的堆棧在上一次調(diào)用時(shí)為空。

So let’s quickly review which returned what value and in what order.

因此，讓我們快速回顧一下哪個(gè)返回了什么值以及返回了什么順序。

rangeOfNumbers(1,1) → returns [1] rangeOfNumbers(1,2) → returns [1,2] rangeOfNumbers(1,3) → returns [1,2,3] rangeOfNumbers(1,4) → returns [1,2,3,4] rangeOfNumbers(1,5) → returns [1,2,3,4,5]

If this is still confusing, firstly I understand – it’s a confusing topic. Next I would recommend typing in your code into this great tool: http://www.pythontutor.com/javascript.html

如果這仍然令人困惑，那么我首先要理解-這是一個(gè)令人困惑的話題。 接下來，我建議您在此出色的工具中輸入代碼： http : //www.pythontutor.com/javascript.html

This is all able to work because we started with a small base case and we essentially built our way back up. Each time our return value is a bit bigger than it was on its previous call, much like if you were to perform this same operation with a for loop.

這一切都是可行的，因?yàn)槲覀儚囊粋€(gè)小的基本案例入手，并且基本上建立了自己的備份方式。 每次我們的返回值都比上一次調(diào)用大，就像您要使用for循環(huán)執(zhí)行相同的操作一樣。

Have any questions? Feel free to ask me on Twitter: @NehemiahKiv

有什么問題嗎？ 隨時(shí)在Twitter上問我： @NehemiahK iv

翻譯自: https://www.freecodecamp.org/news/learn-recursion-in-javascript-by-example/

遞歸javascript

總結(jié)

以上是生活随笔為你收集整理的递归javascript_使用freeCodeCamp挑战解释了JavaScript中的递归的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。