Рекурсия на основе корутин.

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

У корутин есть классное решение, объединяющее преимущества обеих подходов:

// я опустил generic типы для лаконичности
val factorial = DeepRecursiveFunction { num ->
  if (num == 0) 1 
  else num * callRecursive(num - 1)
}
println(factorial.invoke(10))

При вызове DeepRecursiveFunction.invoke() под капотом создается DeepRecursiveScopeImpl, где запускается бесконечный цикл:

class DeepRecursiveScopeImpl<T, R>(
  // это тело DeepRecursiveFunction
  block: suspend DeepRecursiveScope<T, R>.(T) -> R
) : Continuation<R> {

  private var cont = this

  suspend fun callRecursive(value: T): R {
    // тут сохраняется Continuation для текущего вызова рекурсии, каждый последующий Continuation ссылается на предыдущий
  }

  override fun resumeWith(...) {
    // когда рекурсия доходит до базового случая, результат передается с самого последнего Continuation объекта до самого первого, которым является сам класс DeepRecursiveScopeImpl, в итоге ссылка на Continuation зануляется, а бесконечный цикл возвращает конечный результат
  }

  fun runCallLoop(): R {
    while (true) {
      // при каждом шаге цикла создается Continuation для каждого вызова рекурсии, это происходит до тех пор пока block не вернет базовый случай
    }
  }

}

В отличии от привычной нам рекурсии, где каждый шаг хранился в стэке, здесь он хранится в Continuation объекте, то есть вместо стэковой памяти используется heap память.

P.S. Буду благодарен если пройдете опрос и напомимаю о втором своем канале, где пишу обо всем.

Всех с наступающим Новым годом!