遞歸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中的遞歸。 我不會在這里給出完整的定義，但是您可以看看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.

出于本文的目的，讓我們同意我們正在嘗試通過使用一個將自身調用的函數來解決問題。

挑戰 (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算法和數據結構— Basic Javascript部分的最后 ，您遇到了一個有趣的問題：“使用遞歸創建數字范圍”，其說明如下：

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.

我們定義了一個帶有兩個參數的名為rangeOfNumbers的函數。 該函數應返回一個整數數組，該數組以startNum參數表示的數字開頭，以endNum參數表示的數字結尾。 起始編號將始終小于或等于終止編號。 您的函數必須通過調用自身來使用遞歸，而不能使用任何形式的循環。 它還適用于startNum和endNum相同的情況。

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

聽起來很簡單–如果要運行rangeOfNumbers(1，5)，它應該返回[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.

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

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.

劇透警報：您會在下面立即找到答案。 但這并不會破壞太多，因為答案很容易在互聯網上找到。

我的解決方案 (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.

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

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.

我發現棘手的是確切地了解調用堆棧如何工作以及如何返回我的值。

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

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

調用堆棧 (The Call Stack)

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

首先要了解的是調用堆棧如何工作。 我將向您介紹Mozilla開發人員網絡的解釋 ：

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

當腳本調用函數時，解釋器將其添加到調用堆棧中，然后開始執行該函數。

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

當腳本調用函數時，解釋器將其添加到調用堆棧中，然后開始執行該函數。

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

該函數調用的所有函數都會進一步添加到調用堆棧中，并在到達其調用的位置運行。

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

該函數調用的所有函數都會進一步添加到調用堆棧中，并在到達其調用的位置運行。

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

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

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

首先，使用以下值創建并執行rangeOfNumbers —執行上下文：

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.

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

檢查我們的通話堆棧 (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)將是堆棧中的最后一個，因為最后，此調用將返回一個值，使我們可以繼續執行堆棧中的下一個函數。

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]，正如我們已經假定的那樣，因為它是我們的基本情況。 現在，我們從堆棧中彈出rangeOfNumbers(1,1) ，然后返回到距離rangeOfNumbers(1,2)不遠的地方…

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數組。 這樣就給了我們[1,2]個數字，現在我們返回了值。

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)中的下一個調用繼續。 Numbers當前為[1,2]，因為那是rangeOfNumbers(1,2)的返回值。 這就是我們在調用rangeOfNumbers(1,3)時插入的內容，因為再次將3減去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.

得到它了？ 大！ 如果不理解，請重新閱讀本段，因為這是最難理解的部分。

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

如果您要加快速度，那就繼續吧。 如果單擊上方的那部分，其余部分應該會很容易。

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數組當前為[1,2]，因此我們將endNum推為3。現在我們有了[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.

我們如何獲得rangeOfNumbers(1,3)？ 沒錯，從我們調用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.

現在我們將endNum(也稱為4)壓入數字數組，得到[1,2,3,4]并返回此值。 讓我們再次從堆棧中刪除此函數調用，因為它滿足了我們的需求。

匯集全部 (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.

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

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

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

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

如果這仍然令人困惑，那么我首先要理解-這是一個令人困惑的話題。 接下來，我建議您在此出色的工具中輸入代碼： 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.

這一切都是可行的，因為我們從一個小的基本案例入手，并且基本上建立了自己的備份方式。 每次我們的返回值都比上一次調用大，就像您要使用for循環執行相同的操作一樣。

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

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

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

遞歸javascript