递归的边界是什么? [英] 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)
}

模式是

• 递归；
• 尾调用优化；
• 迭代；
• 碰巧引用自身的非终止过程；

或;上面未列出的其他常见模式?

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 发布其参数函数，以在事件循环的下一个¹ 循环中执行.
• then 发布它的参数函数，以便在事件循环的下一个循环中执行.

• 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.

还需要对 Promise 有很好的了解，例如知道 then 返回一个新的 Promise.

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")(或者更好的是包含它的闭包)，它将承诺设置为已解决并安排其在下一个循环中的延续

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 情况.

resolve ends we have again a run-to-completion situation.

 Execution stack                      Event loop messages

                                      console.log

console.log 被执行.实际上，执行了一个调用console.log的函数，这个函数是在调用then时由promise对象设置的.
当 console.log 返回它的 promise 时，它​​会解析并且 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 的第一个版本称为 scheduled.

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 是代码的一个属性，但此代码不是 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.

它在编程意义上也不是迭代(而在理论上它是)，因为迭代是通过特定结构(如for)实现的code>、while、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屋！