递归的界限是什么？ [英] What are the boundaries of recursion?

问题描述

给定

let doAsynchronousStuff = () => {
  return new Promise(resolve => {
    setTimeout(() => {
      resolve("abcdefg"[Math.floor(Math.random() * 7)])
    }, Math.PI * 1 + Math.random())
  })
  .then(data => console.log(data))
  .then(doAsynchronousStuff)
}

该模式是

• 递归;


• 尾调用优化;


• 迭代;


• 一个恰好引用自身的非终止程序;

• recursion;
• tail-call optimization;
• iteration;
• a non-terminating procedure that happens to refer to itself;

或;上面没有列出的其他常见模式？

or; other common pattern that is not listed above?

寻找可靠和/或官方来源的答案。

Looking for an answer drawing from credible and/or official sources.

推荐答案

我重写了代码，删除了所有不相关的东西，并使用我认为在这种情况下更具可读性和风格的样式。

I rewrote the code eliminating all non relevant stuff and using a style I feel is more readable and appeasing in this context.

function doAsynchronousStuff()
{
   return new Promise((resolve, reject) => 
   {
      setTimeout(() => {resolve("test")}, 0)
   })
  .then(console.log)
  .then(doAsynchronousStuff);
}

我们应该分析执行流程，记住JS有一个事件循环，特别是

We should analyze the execution flow remembering that JS has an event loop, particularly

• setTimeout 发布其参数函数，以便在事件循环的下一个 ¹ 循环中执行。


• 然后发布其参数函数，以便在事件循环的下一个周期执行。

• setTimeout posts its argument function to be executed on the next¹ cycle of the event loop.
• then posts its argument function to be executed on the next cycle of the event loop.

事件循环的存在很重要，因为函数在重新进入循环之前将消息发送到 run-to-completion 。

The existence of the event loop is important because the function posting message onto it run-to-completion before the loop is re-entered.

还需要很好地了解承诺，例如知道然后会返回新的承诺。

Also a good knowledge of promises is required, for example knowing that then returns a new promise.

执行 doAsynchronousStuff 时，构造 Promise 对象及其参数函数立即调用。

When doAsynchronousStuff is executed the Promise object is constructed and its argument function is called immediately.

Execution stack                      Event loop messages

doAsynchronousStuff
Promise constructor
Closure (resolve, reject)

这又是 setTimeout 发布一个事件并返回。

This is in turn calls setTimeout that post an event and returns.

Execution stack                      Event loop messages

doAsynchronousStuff                  resolve("test")
Promise constructor
Closure (resolve, reject)
setTimeout

执行回退到 doAsynchronousStuff 设置 Promise 对象的延续，但不是当然要执行它们。所以最后 doAsynchronousStuff 返回，我们有一个 run-to-completion 情况。

The execution falls back to doAsynchronousStuff that set the continuations for the Promise objects but doesn't execute them of course. So in the end doAsynchronousStuff returns and we have a run-to-completion situation.

Execution stack                      Event loop messages

                                     resolve("test")

事件循环执行 resolve（test）（或更好的包含它的闭包）将promise设置为已解决并安排其继续下一个周期

The event loop executes resolve("test") (or better the closure that contains it) which set the promise as resolved and schedule its continuation on the next cycle

 Execution stack                      Event loop messages

 resolve                              console.log

resolve 我们再次结束 run-to -completion 情况。

 Execution stack                      Event loop messages

                                      console.log

console.log 已执行。实际上，执行一个调用 console.log 的函数，当调用然后时，这个函数由promise对象设置。$
当 console.log 返回其承诺时，会在事件上发布 doAsynchronousStuff 循环。

console.log is executed. Actually, a function that calls console.log is executed, this function is set by the promise object when then is called.
When console.log returns its promise resolves and the doAsynchronousStuff is posted on the event loop.

 Execution stack                      Event loop messages

 resolve                              doAsynchronousStuff

当 resolve 结束时，我们有一个 run-to-completion 和 doAsynchronousStuff 再次执行。

When resolve ends we have a run-to-completion and doAsynchronousStuff is executed once again.

现在我赢了在你的问题中，在数学意义上或在CS理论意义上对列表中的术语进行过多挖掘，这样做没有实际的好处，因为我不认为这是一个理论问题。

我会将自己限制在编程的角度。

Now I won't dig too much in the mathematical sense nor in the CS theoretical sense of the terms in the list in your question, doing such would have no practical benefits as I don't believe this is a theoretical question.
I will instead limit myself to a programming point of view.

当第二个 doAsynchronousStuff 实例被称为第一个已经过去了（它 run-to-completion ）。

基本上这种情况相当于这样做

By the time the second doAsynchronousStuff instance is called the first one is long gone (it run-to-completion).
Basically the situation is equivalent to doing this

let f = () => { console.log('hi!'); setTimeout(f, 0); }

我不会将此函数称为递归，因为递归意味着破坏将问题转化为较小的自动相似部分。

递归函数不必直接调用自身，也不必使堆栈增长，但必须按照术语定义本身。

I wouldn't call this function recursive since recursion implies a destruction of a problem into smaller auto-similar parts.
A recursive function doesn't have to call itself directly or doesn't have to "make the stack grow" but it must be defined in terms of itself.

如果它就像

let f = () => { f(); }

我称之为（严重）递归。它是什么？

我想说一个函数在编程意义上是递归的，如果你没有完成它自己所做的所有调用就无法完成它。

第一个例子可以在不等待 f 的后续调用完成的情况下完成，而第二个例子则不能完成。

在我看来我打电话给第一个版本 f ，预定。

I'd call it (badly) recursive. So what is it?
I'd like to say that a function is recursive in the programming sense if you can't complete it without completing all the calls to itself it makes.
The first example can be completed without waiting for the subsequent invocations of f to complete, the second one instead cannot.
In my mind I call the first version of f, scheduled.

关于尾部调用优化，它与此无关。

TCO转换特定内容转发到循环中，它是一个编译器优化而不是代码的属性。

tail-call 是代码的属性，但是这个代码不是尾调用，因为它首先不是递归的。

Regarding tail-call optimization, it has nothing to do with this.
TCO transform a particular kind of recursion into a loop, it is a compiler optimization not a property of the code.
The tail-call is a property of the code, but this code is not tail-call as it is not recursive in the first place.

它也是不是迭代在编程意义上（虽然在理论意义上它是），因为 itera使用特定结构实现（例如用于，，而， goto ）。

这里的边界模糊，因为迭代，递归和调度重叠。

It is also not iteration in the programming sense (while in the theoretical sense it is) since iteration is achieved with specific constructs (like for, while, goto).
The boundary is blurry here as iteration, recursion and scheduling overlaps.

最后，这肯定是一个恰好引用自身的非终止程序的情况。

Finally this is certainly the case of a non-terminating procedure that happens to refer to itself.

¹ 我们在这里进行简化，它不是非常下一个周期，它只是一个未来周期。

¹ We make a simplification here, it has not to be the very next cycle, it is just a future cycle.

这篇关于递归的界限是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！