Является ли асинхронный вызов рекурсией?

#рекурсия #любой_язык #терминология

Определение рекурсии говорит, что это прямой или косвенный вызов функции из себя.

Т. о. функция go в следующем примере рекурсивна:



function pass(f, i) {
  return f(i);
}

function go(i) {
  if (i < 3) {
    console.log(i);
    pass(go, i + 1);
  } else {
    console.log(new Error().stack);
  }
}

go(0);
html .as-console-wrapper { top: 0; max-height: none; }




А теперь заменим функцию pass на асинхронную операцию:



function go(i) {
  if (i < 3) {
    console.log(i);
    setTimeout(go, 0, i + 1);
  } else {
    console.log(new Error().stack);
  }
}

go(0);
html .as-console-wrapper { top: 0; max-height: none; }




Что изменилось? В первом случае стек вызовов содержал цепочку go-pass-go-pass-go-pass-go,
а во втором там только одна функция - go. Асинхронная операция помещается в очередь
операций и при вызове не вложена в то, что её планировало.

Верно ли такой вызов называть рекурсивным?

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

Ответы

Ответ 1

Обычно такое поведение называют асинхронной рекурсией. Между синхронным и асинхронным
кодом существует изоморфизм, и асинхронная рекурсия изоморфна обычной рекурсии.

Изоморфизм, к слову, довольно простой, и "на пальцах" проще всего его объяснить на
примере обещаний. Если есть код вида

function foo() {
  // stage1
  var promise = stage2async();
  stage3sync();
  return promise;
}


то он его приведет к вот такому виду:

function foo() {
  // stage1
  var promise = stage3async();
  stage2sync();
  return promise;
}


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

Существование такого изоморфизма, в том числе, означает, что любые проблемы обычной
рекурсии могут всплыть и в асинхронной версии. Другое дело, что асинхронные решения
обычно меньше подвержены сопутствующим проблемам благодаря тому, что асинхронный поток
"дешевле" системного.

Например, переполнение стека.

Обычная рекурсия может запросто переполнить стек. Асинхронная рекурсия такому, казалось
бы, не подвержена...

...до тех пор пока для возврата значения мы не начинаем собирать "сосиску" из обратных
вызовов. Или пока платформа не начнет в целях диагностики отслеживать асинхронный стек
вызовов, что может привести к утечке памяти. 

Кстати, Google Chrome в своей реализации Promise асинхронный стек вызовов отслеживает
- и это даже очень удобно. Пока не возникнет утечка памяти из-за бесконечной асинхронной
рекурсии.


Ответ 2

И мне думается, что это не рекурсия, а unrolling итерации.

Рекурсия предполагает (опять же imho) возврат в вызывавший контекст. Если из него
 тоже сразу возвращаемся, то получаем хвостовую рекурсию, которая может быть преобразована
компилятором в цикл.