本文共 6319 字,大约阅读时间需要 21 分钟。
java 快速排序 递归
The function calls itself until someone stops it.
该函数将自行调用,直到有人停止它为止。
Recursion can feel difficult to new developers. Perhaps that's because many resources teach it using algorithmic examples (Fibonacci, linked-lists). This piece will hopefully introduce things plainly, using one simple example.
对于新开发人员而言,递归可能会感到困难。 也许是因为许多资源都使用算法示例(斐波纳契(Fibonacci),链接列表)来教它。 希望通过一个简单的例子,这篇文章将简单地介绍一下。
Recursion is when a function calls itself until someone stops it. If no one stops it then it'll recurse (call itself) forever.
递归是指函数调用自身直到有人停止它。 如果没有人停止,它将永远递归 (自称)。
Recursive functions let you perform a unit of work multiple times. This is exactly what for/while
loops let us accomplish! Sometimes, however, recursive solutions are a more elegant approach to solving a problem.
递归函数使您可以多次执行一个工作单元。 这正是for/while
循环让我们完成的! 但是,有时递归解决方案是解决问题的一种更优雅的方法。
Let's create a function that counts down from a given number. We'll use it like this.
让我们创建一个从给定数字开始倒数的函数。 我们将像这样使用它。
countDownFrom(5);// 5// 4// 3// 2// 1
And here's our algorithm to solve this problem.
这是我们解决此问题的算法。
Take one parameter called number
. This is our starting point.
取一个称为number
参数。 这是我们的出发点。
Go from number
down to 0
, logging each one along the way.
从number
降低到0
,并沿途记录每个number
。
We'll start with a for
loop approach and then compare it to a recursive one.
我们将从for
循环方法开始,然后将其与递归方法进行比较。
function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); } }countDownFrom(5);// 5// 4// 3// 2// 1
This one contains both algorithmic steps.
这包含两个算法步骤。
✅ Take one parameter called number
.
✅取一个称为number
参数。
✅ Log everything from number
to 0
.
✅记录从number
到0
所有内容。
function countDownFrom(number) { if (number === 0) { return; } console.log(number); countDownFrom(number - 1);}countDownFrom(5);// 5// 4// 3// 2// 1
This one also passes.
这也过去了。
✅ Take one parameter called number
.
✅取一个称为number
参数。
✅ Log everything from number
to 0
.
✅记录从number
到0
所有内容。
So conceptually the two approaches are the same. However, they get the job done in different ways.
因此,从概念上讲,这两种方法是相同的。 但是,他们以不同的方式完成工作。
For a more visual example, let's put a debugger
in our loop version and throw it into Chrome Developer Tools.
对于更直观的示例,让我们在循环版本中放入debugger
,然后将其放入Chrome开发者工具中。
function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } }
See how it uses an extra variable, i
, to track the current number? As you iterate i
decreases, eventually hitting 0
and terminating.
看看它如何使用额外的变量i
来跟踪当前数字吗? 随着您的迭代, i
逐渐减少,最终达到0
并终止。
And in the for
loop we specified "stop if i > 0
".
在for
循环中,我们指定“如果i > 0
停止”。
function countDownFrom(number) { if (number === 0) { return; } console.log(number); debugger; countDownFrom(number - 1);}
The recursive version doesn't need extra variables to track its progress. Notice how the pile of functions (call stack) grows as we recurse?
递归版本不需要额外的变量来跟踪其进度。 注意我们递归时函数堆( 调用堆栈 )如何增长?
That's because each call to countDownFrom
adds to the stack, feeding it number - 1
. By doing this we're we're passing along an updated number
each time. No extra state needed!
这是因为对countDownFrom
的每次调用countDownFrom
添加到堆栈中,并向其提供number - 1
。 通过这样做,我们每次都传递一个更新的number
。 不需要额外的状态!
That's main difference between the two approaches.
这是两种方法之间的主要区别。
But how does either version know when to stop?
但是,哪个版本知道何时停止?
In your travels, you may have been warned about the dreaded infinite loop.
在旅行中,您可能已经被警告过可怕的无限循环。
🚨 THIS RUNS FOREVER, BE WARNED 🚨while (true) { console.log('WHY DID YOU RUN THIS?!' }🚨 THIS RUNS FOREVER, BE WARNED 🚨for (i = 0;;) { console.log('WHY DID YOU RUN THIS?!') }
Since they'd theoretically run forever, an infinite loop will halt your program and possibly crash your browser. You can prevent them by always coding a stopping condition.
由于理论上它们将永远运行,因此无限循环将暂停您的程序,并可能导致浏览器崩溃。 您可以通过始终编写停止条件来防止它们发生。
✅ This does not run foreverx = 0;while (x < 3) { console.log(x); x++; }✅ This does not run foreverfor (x = 0; x < 3; x++) { console.log(x); }
In both cases we log x
, increment it, and stop when it becomes 3
. Our countDownFrom
function had similar logic.
在这两种情况下,我们都记录x
,递增x
,然后在x
变为3
时停止。 我们的countDownFrom
函数具有类似的逻辑。
// Stop at 0for (let i = number; i > 0; i--)
Again, loops need extra state to determine when they should stop. That's what x
and i
are for.
同样,循环需要额外的状态来确定何时停止。 这就是x
和i
是。
Recursion also presents the same danger. It's not hard to write a self-referencing function that'll crash your browser.
递归也存在同样的危险。 编写会导致浏览器崩溃的自引用功能并不难。
🚨THIS RUNS FOREVER, BE WARNED🚨function run() { console.log('running'); run();}run();// running// running// ...
Without a stopping condition, run
will forever call itself. You can fix that with an if
statement.
在没有停止条件的情况下, run
将永远自我调用。 您可以使用if
语句解决该问题。
✅ This does not run foreverfunction run(x) { if (x === 3) return; console.log('running'); run(x + 1);}run(0);// running// running// running// x is 3 now, we're done.
This is known as the base case–our recursive countDownFrom
had one.
这被称为基本案例–我们的递归countDownFrom
有一个。
if (number === 0) { return;}
It's the same idea as our loop's stopping logic. Whichever approach you pick, always remember that at some point it needs to be stopped.
这与循环的停止逻辑相同。 无论选择哪种方法,请始终记住,必须在某个时候停止它 。
A base case is a condition that stops the recursion. Don't forget to add them!
基本情况是停止递归的条件。 不要忘记添加它们!
For more content like this, check out . And please let me know what else you'd like to see!
有关此类的更多内容,请访问 。 并且,请让我知道您还想看到什么!
Until next time!
直到下一次!
翻译自:
java 快速排序 递归
转载地址:http://vshwd.baihongyu.com/