递归 尾递归

by Michael Olorunnisola

通过Michael Olorunnisola

递归，递归，递归 (Recursion, Recursion, Recursion)

Before I tell you what recursion is, you should read this article:

在我告诉您什么是递归之前，您应该阅读以下文章：

Give yourself a pat on the back if you didn’t fall for that one. If you did, no worries — you now know what recursion is!

如果您不喜欢那个，请给自己一个拍子。 如果您这样做了，那就不用担心-您现在知道什么是递归了！

People often joke that in order to understand recursion, you must first understand recursion. — John D. Cook

人们经常开玩笑说，为了了解递归，您必须首先了解递归。 约翰·库克(John D. Cook)

When I first started coding, I thought about recursion all the time. I used to think of it as some magic spell, or some higher order technique that only the best of the best developers used to solve the hardest problems.

当我第一次开始编码时，我一直都在考虑递归。 我曾经将其视为某种魔术，或一些仅由最好的开发人员中的最好的人用来解决最棘手的问题的高级技术。

As it turns out, it’s not magic at all. But good developers do understand it. And great developers understand when it’s best to use it.

事实证明，这根本不是魔术。 但是优秀的开发人员确实了解它。 优秀的开发人员了解何时最佳使用它。

So what exactly is recursion?

那么递归到底是什么呢？

Have you ever practiced something over and over again until the point where you “got it down?” Then you’ve preformed a recursive act.

您是否曾经一遍又一遍地练习某些东西，直到您“忘了它”？ 然后，您已经执行了递归操作。

Plainly speaking, you executed a task or series of steps repeatedly until you reached some desired goal. That, my friends, is the essence of recursion.

概括地说，您重复执行了一项任务或一系列步骤，直到达到某个期望的目标。 我的朋友们，那是递归的本质。

In code speak, a recursive function is a function which calls itself.

用代码来讲，递归函数是一个调用自身的函数。

Before we jump into any code, let’s walk through a basic example to understand the structure of recursive functions. Since the piano is near and dear to my heart, we will make a function called practicePiano.

在进入任何代码之前，让我们看一个基本的例子来理解递归函数的结构。 由于钢琴是我亲爱的亲爱的，因此我们将创建一个称为PracticePiano的功能。

Every time this function is called with a person, that person will practice the piano. Since I don’t spend enough time practicing right now, I should get a little practice in.

每次有人呼叫此功能时，该人都会练习钢琴。 由于我现在没有花足够的时间练习，因此我应该进行一些练习。

practicePiano(person){  practiceScales(person);    practiceChords(person);}

practicePiano('Michael');

I’ve called the function above once, so I was able to get one session in, but I definitely need more than one to really get better.

我已经调用了上面的函数一次，因此能够参加一个会议，但要真正变得更好，我肯定需要多个会议。

practicePiano('Michael');practicePiano('Michael');practicePiano('Michael');practicePiano('Michael');practicePiano('Michael');practicePiano('Michael');practicePiano('Michael');practicePiano('Michael');...

This is great and all, but it breaks one of programming’s greatest tenets: Don’t Repeat Yourself (DRY).

固然很好，但它打破了编程的最大宗旨之一：不要重复自己(DRY)。

I was able to get more practice sessions in, but every time I want to practice more, I have to add another call to practicePiano.

我可以参加更多的练习班，但是每次我想练习更多时，我都必须再添加一个练习钢琴的电话。

One way we can solve this problem is by calling the function within itself, so every time I practicePiano, I practice more:

解决这个问题的一种方法是在内部调用函数，因此每次我练习钢琴时，我都会练习更多：

practicePiano(person){  practiceScales(person);    practiceChords(person);

//Recursive magic here!

practicePiano(person);}

//Now we only need one of these!

practicePiano('Michael');

This is awesome! I only have to call it once. The only problem is, once I call this function… I never stop practicing. I never stop until it is literally impossible for me to practice anymore.

这太棒了！ 我只需要打一次。 唯一的问题是，一旦调用此函数，我就永远不会停止练习。 我永不停止，直到我再也无法练习为止。

//Our code above would behave as follows:

practiceScales('Michael');    practiceChords('Michael');

//Recursive Call

practiceScales('Michael');    practiceChords('Michael');

//Recursive Call

practiceScales('Michael');    practiceChords('Michael');

//Recursive Call

//..till I can't physically practice anymore

When your computer reaches a similar point where it’s unable to continue it usually returns this error:

当计算机到达无法继续的类似点时，通常会返回此错误：

RangeError: Maximum call stack size exceeded

That is the equivalent of your computer saying, “I’ve run out of space, and had to close up shop.” It has recorded each function call in memory in a stack. But since the calls never stop, the stack gets completely filled and the computer is forced to stop. (This is where the name for the popular website, Stack Overflow, comes from.)

这相当于您的计算机说：“我的空间用完了，不得不关门了。” 它已将每个函数调用记录在堆栈中的内存中。 但是由于调用永不停止，因此堆栈已完全装满，并且计算机被迫停止。 (这是流行网站的名称Stack Overflow的来源。)

So going back to my never ending piano practice, how can we keep my hands from falling off?

那么回到我永无止境的钢琴练习中，我们如何才能防止手掉下来呢？

This is where we see the importance of a term you may have heard before: the base case.

在这里，我们可以看到您之前可能听说过的术语的重要性： 基本案例 。

In recursive functions the base case is the goal you are trying to achieve or the task you are looking to complete. The base case’s job is to tell your function when it should stop.

在递归函数中，基本情况是您要尝试实现的目标或要完成的任务。 基本案例的工作是告诉您的函数何时应该停止。

In our analogy, that goal can be practicing until I’m tired.

打个比方，这个目标可以一直练习直到我累了。

practicePiano(person){   if (tired(person)){ //When I am finally tired    console.log("Guess you can take a break now...");    return ;  //This will return out of the function and stop the recursive call  }

practiceScales(person);    practiceChords(person);

//Recursive magic here!

practicePiano(person);}

//Now when we call this here...I'll only practice over and over again until I'm tired

practicePiano('Michael');

This is where most developers run into problems. Although our current piano practice analogy is a simplification, it drives home an extremely important point: what if I never got tired of practicing? Then the base case we wrote would not resolve our “Maximum call stack size exceeded” error.

这是大多数开发人员遇到问题的地方。 尽管我们目前的钢琴练习类比只是一种简化，但它带给我一个极其重要的观点：如果我从不厌倦练习，该怎么办？ 这样，我们编写的基本案例将无法解决“超出最大调用堆栈大小”错误。

Before we jump straight into coding, it’s important to take the time to reflect on all the possible situations that can — and should — stop our recursive calls.

在我们直接进行编码之前，重要的是要花时间思考所有可能并且应该停止递归调用的情况。

As a developer, you’ll write complex algorithms, which may take variable inputs and use recursion to achieve some goal.

作为开发人员，您将编写复杂的算法，这些算法可能需要可变的输入并使用递归来实现某些目标。

You may develop a base case or multiple base cases that you believe will be reached by your recursive call. But that may not always be the case.

您可以开发一个或多个您认为递归调用可以达到的基本案例。 但这并非总是如此。

Consider the case of my cyborg counterpart:

考虑我的机器人机器人的情况：

practicePiano(person){   if (tired(person)){    console.log("Guess you can take a break now...");    return ;    }

if (handsFallOff(person)){   console.log("Go see a doctor about that");    return ; }

practiceScales(person);    practiceChords(person);

practicePiano(person);}

practicePiano('Cyborg-Michael');

//Cyborg-Michael never gets tired//Nor do his hands ever fall off//Back to being stuck practicing forever...

Given this, it’s important to always make sure you are thorough in developing your base case(s) and certain your function behaves in a way that a base case will always be reached.

鉴于此，重要的是要始终确保开发完基本案例并确保您的函数以始终达到基本案例的方式运行。

In our example, a logical base case would be being able to play some piece like Beethoven’s 5th.

在我们的示例中，一个合乎逻辑的基本案例将是能够演奏一些贝多芬的第五乐。

Refactoring our code, we now have:

重构我们的代码，我们现在有：

practicePiano(person, song){   if (tired(person)){    console.log("Guess you can take a break now...");    return ;    }

if (handsFallOff(person)){   console.log("Go see a doctor about that");    return ; }

if (song(person)){   console.log("Great Job! Time to learn this on the guitar!");    return ; }

practiceScales(person);    practiceChords(person);

practicePiano(person, song);}

practicePiano('Cyborg Michael', BeethovenFifth);

//The Cyborg version of me never gets tired//Nor do my hands ever fall off//But, being a cyborg...I can learn Beethoven's 5th pretty quickly

This is the power of recursive solutions. With a few lines of code, I’m able to achieve some task, for which I may not know how many steps it may take. I may need 100 practice session, whereas my cyborg self will only need 5, but this solution will still work for the both of us.

这就是递归解决方案的力量。 用几行代码，我就能完成一些任务，而我可能不知道它可能要执行多少步骤。 我可能需要进行100次练习，而我的机器人自我只需要5次练习，但此解决方案仍然适用于我们俩。

So to recap, just remember the following:

因此，回顾一下，只需记住以下几点：

1. Recursion allows you to easily repeat a task to accomplish some goal.
   递归使您可以轻松地重复执行任务以实现某些目标。
2. The base case(s) should be thorough enough to allow your recursive function to actually reach a conclusion (and not run forever).
   基本案例应该足够详尽，以使递归函数真正得出结论(而不是永远运行)。
3. Recursion helps you keep your code DRY (again, you’ll hear this acronym a lot, so remember that it stands for “Don’t repeat yourself” —oops, I just did!)
   递归可以帮助您使代码保持DRY(再次，您会听到很多首字母缩写词，因此请记住，它代表“不要重复自己” —哎呀，我就是这样！)

更多递归 (More recursion to come)

We’ll go more in-depth into recursion in my upcoming series on data structures. During this deep dive, we’ll get a look into how you can start to use and recursion in your everyday code. We’ll also work through various looping methods to understand why it may be better to use one over the other.

在我即将发布的有关数据结构的系列文章中，我们将更深入地介绍递归。 在这次深入学习中，我们将研究如何开始在日常代码中使用和递归。 我们还将研究各种循环方法，以了解为什么使用一种优于另一种可能更好。

As an aside, one of the topics we didn’t get a chance to cover here are problems. Factorial problems are where you find recursive solutions applied most often as they require recursively iterating some defined number of times. You can find more specifics regarding solving factorial problems in this by SitePoint.

顺便说一句，这里我们没有机会讨论的主题之一是问题。 阶乘问题是您发现递归解决方案最常用的地方，因为它们需要递归地迭代一定的次数。 您可以在SitePoint的这篇找到有关解决阶乘问题的更多详细信息。

Here are some additional resources to help out:

这里有一些其他资源可以帮助您：

Also, thanks to for helping edit this.

另外，还要感谢的帮助。

翻译自:

递归 尾递归