Достижение рекурсии без стека в Java 8

Question

Как достичь рекурсии без стекол в Java?

Слово, которое, кажется, больше всего подходит, «батут», и я не знаю, что это значит.

Может кто-нибудь В ДЕТАЛИ объясните, как достичь рекурсии без стекол в Java? Кроме того, что такое «батут»?

Если вы не можете предоставить ни один из них, не могли бы вы указать мне в правильном направлении (то есть книгу, чтобы прочитать об этом или какой-то учебник, который учит всем этим понятиям)?

Answer 1

Батут - это образец для преобразования рекурсии на основе стека в эквивалентный цикл. Поскольку циклы не добавляют фреймы стека, это можно рассматривать как форму безрекурсивной рекурсии.

Вот схема я нашел полезным:

bartdesmet.net От

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

---

Рассмотрим этот стек на основе рекурсии:

public static int factorial(final int n) { 
    if (n <= 1) { 
     return 1; 
    } 
    return n * factorial(n - 1); 
} 

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

К счастью, мы можем выразить эту функцию в виде цикла:

public static int factorial2(int n) { 
    int i = 1; 
    while (n > 1) { 
     i = i * n; 
     n--; 
    } 
    return i; 
} 

Что здесь происходит? Мы сделали рекурсивный шаг и сделали его итерацией внутри цикла. Мы завершаем цикл, пока не завершим все рекурсивные шаги, сохраняя результат или каждую итерацию в переменной.

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

Обобщение этого рисунка - батут.

public class Trampoline<T> 
{ 
    public T getValue() { 
     throw new RuntimeException("Not implemented"); 
    } 

    public Optional<Trampoline<T>> nextTrampoline() { 
     return Optional.empty(); 
    } 

    public final T compute() { 
     Trampoline<T> trampoline = this; 

     while (trampoline.nextTrampoline().isPresent()) { 
      trampoline = trampoline.nextTrampoline().get(); 
     } 

     return trampoline.getValue(); 
    } 
} 

Trampoline требует двух членов:

• значение текущего шага;
• следующая функция не вычислить, или ничего, если мы достигли последнего шага

Любое вычисление, которое можно описать таким образом, может быть «trampolined».

Как это выглядит для факториала?

public final class Factorial 
{ 
    public static Trampoline<Integer> createTrampoline(final int n, final int sum) 
    { 
     if (n == 1) { 
      return new Trampoline<Integer>() { 
       public Integer getValue() { return sum; } 
      }; 
     } 

     return new Trampoline<Integer>() { 
      public Optional<Trampoline<Integer>> nextTrampoline() { 
       return Optional.of(createTrampoline(n - 1, sum * n)); 
      } 
     }; 
    } 
} 

И называть:

Factorial.createTrampoline(4, 1).compute() 

---

Примечания

• Boxing сделает это неэффективно в Java.
• Этот код был написан на SO; он не был проверен или даже составлен

Дальнейшее чтение

• Java Basics: How Call Works
• Stacks and Recursion Elimination
• Wikipedia
• Jumping the Trampoline in C# – Stack-Friendly Recursion
• Reverse Trampoline
• What is a trampoline function?