递归的边界是什么？

Question

给出

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)
}

模式是

的实现吗

递归；
尾调用优化；
迭代；
一个恰好引用自身的非终止过程；

或；上面未列出的其他常见模式？

正在从可靠的 and/or 官方来源寻找答案。

Answer 1

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

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

我们应该分析执行流程记住JS有an event loop，特别是

setTimeout post它的参数函数将在事件循环的下一个¹周期执行。
then post它的参数函数将在事件循环的下一个周期执行。

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

还需要对 promise 有很好的了解，例如知道 then returns 一个新的 promise。

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

Execution stack                      Event loop messages

doAsynchronousStuff
Promise constructor
Closure (resolve, reject)

这又调用了 setTimeout 那个 post 事件和 returns.

Execution stack                      Event loop messages

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

执行回退到 doAsynchronousStuff，它为 Promise 对象设置了延续，但当然不会执行它们。所以最后 doAsynchronousStuff returns 我们有一个 运行-to-completion 的情况。

Execution stack                      Event loop messages

                                     resolve("test")

事件循环执行 resolve("test")（或更好的包含它的闭包），将承诺设置为已解决并安排在下一个周期继续

 Execution stack                      Event loop messages

 resolve                              console.log

resolve 结束我们又遇到了 运行-完成 的情况。

 Execution stack                      Event loop messages

                                      console.log

console.log 被执行。实际上，执行了一个调用console.log的函数，这个函数是在调用then时由promise对象设置的。
当 console.log returns 它的承诺解决并且 doAsynchronousStuff 在事件循环中被 post 编辑。

 Execution stack                      Event loop messages

 resolve                              doAsynchronousStuff

当 resolve 结束时，我们有一个 运行-to-completion 并且 doAsynchronousStuff 会再次执行。

现在我不会在你问题列表中的术语的数学意义上和 CS 理论意义上挖掘太多，这样做没有实际好处，因为我不认为这是理论上的问题。
相反，我将把自己限制在编程的角度。

当第二个 doAsynchronousStuff 实例被调用时，第一个实例早已消失（运行-to-completion）。
基本上情况相当于这样做

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

我不会将此函数称为递归，因为递归意味着将问题分解为更小的自动相似部分。
递归函数不必直接调用自身或不必 "make the stack grow" 但它必须 根据自身 定义。

如果像

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

我会（糟糕地）称之为递归。那是什么？
我想说一个函数在编程意义上是递归的，如果你不能在不完成它对自身的所有调用的情况下完成它。
第一个示例可以在不等待 f 的后续调用完成的情况下完成，而第二个示例则不能。
在我心中我称第一个版本f,scheduled.

关于tail-call优化，与此无关
TCO transform a particular kind of recursion into a loop，它是一个编译器优化，不是属性的代码。
tail-call是代码的属性，但这段代码不是tail-call，因为它不是递归的第一名.

在编程意义上它也是不是迭代（而在理论意义上它是）因为迭代是通过特定构造实现的（如 for、while、goto）。
由于迭代、递归和调度重叠，边界在这里很模糊。

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

¹我们这里做个简化，不一定是下一个周期，就是未来的周期。

Answer 2

None 以上。所讨论的代码不是递归的，也不是完全迭代的（尽管从英语的角度来看它是迭代的，从我们通常在编程中称之为迭代的观点来看不是，请注意，从英语语言的角度来看，递归是迭代的，但我们并没有说它在编程中），因为它不是递归的短语 "tail-call-optimised" 不适用并且它不是非由于函数以 return.

结尾而终止

它是一个函数，它安排一系列函数在稍后执行，其中一个是它自己。

调度是一种设计模式。调度最古老的例子之一是操作系统执行的进程调度。下一个最古老的例子之一是 cron。

调度的工作原理是运行时间环境（Linux内核，Windows内核，cron进程，javascript）保存一个"database"（可能像链表一样简单，也可能像 SQL 那样高级，或者像文本文件一样技术含量低）某种对代码的引用，它应该运行以及触发它们的条件（查看 AWS Lambda 服务以获得该想法的高级实现）并定期以某种方式检查是否满足条件然后执行代码。

对于 OS 内核，条件集包括某种公平算法以确保所有程序都能使用 CPU。对于 cron，条件是 crontab 中的时间规范。对于 javascript，条件是注册回调的事件（对于 setTimeout，它是超时事件）。

传统上，如果您要为此编写自己的软件，您会将其编写为一个简单的状态机。以下是类似 C 的伪代码，实现了与上面示例相同的东西

int tick = 0;

// Assume that there is an API for registering 1ms periodic interrupt
interrupt_1ms periodic () {
    tick++;
}

int main (void) {
    int timeout = PI + rand(); // a fairly silly way to randomly select 3 or 4 ms
    char state = 0;
    char result = nul;
    char* data = "abcdefg";

    while (1) {
        if (tick >= timeout && state == 0) {
            state = 1;
            tick = 0;
            timeout = PI + rand();
        }

        switch (state) {
            case 1:
                result = data[floor(rand() * 7)];
                state = 2;
                break;
            case 2:
                printf("%c", result);
                state = 3;
                break;
            case 3:
                state = 0; // reschedule the doAsynchronousStuff
                break;
        }
    }
}

这是一种传统方式。 javascript 所做的并不完全相同，但在概念上相似。它仍然使用永久循环作为事件循环的核心，但它不会连续运行（那会浪费 CPU 时间，加热 CPU 并耗尽电池）。相反，它会阻止调用异步 I/O API（select、poll、epoll、kqueue 等之一 - libuv 将在编译时 select）并将控制权传递给 OS 这将使进程进入休眠状态，直到触发已注册的 I/O 事件之一。

现在，请注意您的代码：

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)
}

我不了解你，但对我来说，它比传统的状态机更容易推理。好的，对于这个非常简单的例子，上面的 C 伪代码很容易理解，但是考虑一个具有数十或数百个复杂事件的真实世界 node.js 或 jQuery 应用程序（在传统 jQuery 应用程序，这些事件甚至可以自行取消安排或安排更多的事件处理程序）。随着你必须处理的事件数量的增加，javascript 的语法变得更易读，即使对于 one 事件，初学者不熟悉匿名函数和异步代码可能更喜欢我的伪 C 示例。

即使是老派的非承诺回调也比伪 C 代码更具可读性：

function doAsynchronousStuff () {
    setTimeout(function () {
      console.log("abcdefg"[Math.floor(Math.random() * 7)]);
      doAsynchronousStuff();
    }, Math.PI * 1 + Math.random());
}

所以语法可能是新的（好吧，不是那么新，Lispers 在 70 年代就已经在做这种事情了）但是这个想法是旧的。由于语法的原因，核心概念可能无法识别，所以不要被语法分心。它只是用计时器安排运行某事。而我们简单的称重复调度为"repeated scheduling"（Google Calendar和Apple Calendar都称他们为"repeat"）。

递归的边界是什么？

What are the boundaries of recursion?

javascript

language-agnostic

recursion

computer-science