Каковы границы рекурсии?

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

ли модель реализация

• рекурсии;
• оптимизация хвостового вызова;
• итерация;
• - процедура без прерывания, которая, как считается, относится к самому себе;

or; другой общий шаблон, который не указан выше?

Ищет ответ из достоверных и/или официальных источников.

Answer 1

Я переписал код, устраняя все не относящиеся к делу вещи и используя стиль, который я чувствую, более читабельным и умиротворяющим в этом контексте.

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

Мы должны анализировать поток выполнения запоминанием, что JS имеет an event loop, в частности

• setTimeout сообщений аргумент функции будет выполняться на следующем цикла цикла событий.
• then публикует свою функцию аргумента, которая должна быть выполнена в следующем цикле цикла события.

Существование цикла событий важно, так как сообщение функции проводки на это вводных к завершению до цикла повторно введено.

Также требуется хорошее знание обещаний, например, зная, что then возвращает новое обещание.

Когда doAsynchronousStuff выполнен, объект Promise построен и его функция аргумента вызывается немедленно.

Execution stack      Event loop messages 

doAsynchronousStuff 
Promise constructor 
Closure (resolve, reject) 

Это в свою очередь вызывает setTimeout что пост событие и возвращается.

Execution stack      Event loop messages 

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

Казни возвращается к doAsynchronousStuff, которые устанавливают продолжения для Promise объектов, но не выполняют их, конечно. Таким образом, в конце doAsynchronousStuff возвращается, и у нас есть Замедление до завершения.

Execution stack      Event loop messages 

            resolve("test") 

Цикл событий выполняет resolve("test") (или лучше замыкание, которое содержит его), который устанавливается обещание как решенный и планировать свое продолжение на следующем цикле

Execution stack      Event loop messages 

resolve        console.log 

resolve заканчивается у нас снова пробега -to-completion положение дел.

Execution stack      Event loop messages 

             console.log 

console.log выполнено. Фактически, выполняется функция, вызывающая console.log, эта функция задается объектом-обещанием при вызове then.
Когда console.log возвращает свое обещание, решает, и doAsynchronousStuff отправляется на контур события.

Execution stack      Event loop messages 

resolve        doAsynchronousStuff 

Когда resolve заканчивается у нас есть вводного к завершению и doAsynchronousStuff выполняется еще раз.

---

Теперь я не буду копать слишком много в математическом смысле, ни в CS теоретическом смысле слова в списке в вашем вопросе, делая такие не будет иметь никаких практических преимуществ, поскольку я не считаю, что это теоретический вопрос.
Вместо этого я буду ограничиваться программированием.

К тому времени, когда второй экземпляр doAsynchronousStuff называется первым, он давно ушел (он завершение до завершения).
В принципе ситуация равносильна делает этот

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

Я бы не назвал эту функцию рекурсивного так рекурсия подразумевает разрушение задачи на более мелкие части авто автомодельного.
Рекурсивная функция не должна называть себя непосредственно или не должна «увеличивать стек», но она должна быть , определенной в терминах самого себя.

Если бы это было как

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

Я бы назвал это (плохо) рекурсивным. Так что это?
Я хотел бы сказать, что функция является рекурсивной в смысле программирования, если вы не можете ее завершить, не выполняя все вызовы, которые она сама делает.
Первый пример может быть завершен, не дожидаясь завершения последующих вызовов f, второй вместо этого не может.
На мой взгляд, я называю первую версию f, запланировано.

Относительно Оптимизация хвостового вызова, это не имеет никакого отношения к этому.
TCO transform a particular kind of recursion into a loop, это оптимизация компилятора не является свойством кода.
tail-call является собственностью кода, но этот код не является tail-call, поскольку он не является рекурсивным в первую очередь.

Также не итерация в смысле программирования (в то время как в теоретическом смысле), так как итерация достигается специфическими конструкциями (например, for, while, goto).
Граница размыта здесь как итерация, рекурсия и планирование перекрытий.

Наконец, это, безусловно, относится к процедуре без прерывания, которая, как считается, относится к самому себе.

---

Мы делаем здесь упрощение, он не должен быть в очень следующий цикл, это просто будущий цикл.

Answer 2

Ничего из перечисленного. Этот код не является рекурсивным, не совсем итеративным (хотя с точки зрения английского языка он итеративен, с точки зрения того, что обычно нормально назвать итеративным в программировании это не так, обратите внимание, что из точки представление о рекурсии на английском языке является итеративным, но мы не говорим, что оно находится в программировании), поскольку оно не является рекурсивным, фраза «оптимизация с помощью хвоста» не применяется и не прерывается, поскольку функция заканчивается возвращение.

Что это такое функция, которая планирует выполнение ряда функций, которые будут выполнены позже, один из которых сам по себе.

Планирование a design pattern. Один из старейших примеров планирования - это планирование процесса, которое делают операционные системы. Одним из следующих старейших примеров является cron.

Как работает планирование, среда выполнения (ядро Linux, ядро ​​Windows, процесс cron, javascript) сохраняет «базу данных» (которая может быть такой же простой, как связанный список или такой высокий уровень, как SQL или как низкотехнологичный текстовый файл) какой-то ссылки на код, который он должен запускать, и условия, которые его запускают (ознакомьтесь с услугой AWS Lambda для очень высокого уровня реализации этой идеи) и периодически как-то проверяет посмотрите, выполняется ли условие, а затем выполните код.

Для ядер ОС в набор условий входит некоторый алгоритм справедливости, гарантирующий, что все программы получат использование ЦП. Для 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 делает не совсем то же самое, но похожее в концепции. Он по-прежнему использует цикл forever как ядро ​​цикла событий, но он не запускается непрерывно (что будет тратить процессорное время, нагревает процессор и сбрасывает батареи). Вместо этого он блокирует вызов одного из асинхронных API ввода-вывода (select, poll, epoll, kqueue и т. Д. - libuv будет выбирать во время компиляции) и передает управление ОС, которое заставляет процесс спать до тех пор, пока один из зарегистрированных I/Вывода.

Теперь обратите внимание, код:

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 дает вам в своем синтаксисе, становится намного читабельнее, хотя для один событие, которое новичок, не знакомый с анонимными функциями и асинхронный код, может предпочесть мой пример псевдо-C.

Даже старая школа, не promisified обратных вызовов более читаемые, чем код псевдо-C:

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

Так синтаксис может быть новым (ну, не то, что новая, Lispers делали такого рода вещь в 70-е годы), но идея старая. Основная концепция может быть не распознаваемой из-за синтаксиса, поэтому не слишком отвлекайтесь на синтаксис. Это просто планирование для запуска чего-то с таймером. И мы просто вызываем повторное планирование «повторное расписание» (как календарь Google, так и Apple Calendar называют их «повторением»).