В этой статье, взятой из книги « Функциональное программирование на Java» , я объясняю, как использовать рекурсию, избегая при этом риска исключения StackOverflow.
Corecursion составляет этапы вычислений, используя выходные данные одного шага в качестве входных данных следующего шага, начиная с первого шага. Рекурсия — это та же операция, но начинающаяся с последнего шага. В этом случае мы должны отложить оценку, пока не встретим базовое условие (соответствующее первому шагу corecursion).
Допустим, у нас есть только две инструкции на нашем языке программирования: увеличение (добавление 1 к значению) и уменьшение (вычитание 1 из значения). Давайте реализуем дополнение, составив эти инструкции.
Corecursive и рекурсивные примеры сложения
Чтобы добавить два числа, x и y, мы можем сделать следующее:
- если
y == 0, вернутьx - в противном случае увеличьте
x, уменьшитеyи начните снова.
Это может быть написано на Java как:
|
1
2
3
4
5
6
7
|
static int add(int x, int y) { while(y > 0) { x = ++x; y = --y; } return x;} |
или проще:
|
1
2
3
4
5
6
|
static int add(int x, int y) { while(y-- > 0) { x = ++x; } return x;} |
Обратите внимание, что нет проблем с непосредственным использованием параметров x и y , поскольку в Java все параметры передаются по значению. Также обратите внимание, что мы использовали пост декрементацию для упрощения кодирования. Однако мы могли бы использовать предварительное декрементирование, слегка изменив условие, таким образом переключая форму с итерацией с y на 1 на итерацию с y‑1 до 0 :
|
1
2
3
4
5
6
|
static int add(int x, int y) { while(--y >= 0) { x = ++x; } return x;} |
Рекурсивная версия сложнее, но все же очень проста:
|
1
2
3
4
5
|
static int addRec(int x, int y) { return y == 0 ? x : addRec(++x, --y);} |
Оба подхода, кажется, работают, но если мы попробуем рекурсивную версию с большими числами, мы можем получить сюрприз. Хотя
|
1
|
addRec(10000, 3); |
выдает ожидаемый результат 10003, переключая параметры, вот так:
|
1
|
addRec(3, 10000); |
создает StackOverflowException .
Как рекурсия реализована в Java?
Чтобы понять, что происходит, мы должны посмотреть, как Java обрабатывает вызовы методов. Когда метод вызывается, Java приостанавливает то, что он в данный момент делает, и помещает среду в стек, чтобы освободить место для выполнения вызываемого метода. Когда этот метод возвращается, Java извлекает стек, чтобы восстановить среду и возобновить выполнение программы. Если мы вызываем один метод за другим, стек всегда будет содержать хотя бы один из этих методов вызова среды.
Но методы составляются не только путем вызова их один за другим. Методы вызывают методы. Если method2 вызывает method2 как часть своей реализации, Java снова приостанавливает выполнение method2 текущую среду в stack и начинает выполнение method2 . Когда method2 возвращается, Java извлекает последнюю method2 среду из стека и возобновляет выполнение (в нашем случае метода method1 ). Когда method1 завершается, Java снова извлекается из стека и возобновляет то, что он делал, прежде чем вызывать этот метод.
Конечно, вызовы методов могут быть глубоко вложенными. Есть ли ограничение на глубину вложения метода? Да. Пределом является размер стека. В современных ситуациях предел составляет где-то несколько тысяч уровней, хотя его можно увеличить, настроив размер стека. Тем не менее, один и тот же размер стека используется для всех потоков, поэтому увеличение размера стека для одного вычисления обычно приводит к потере пространства. Размер стека по умолчанию варьируется от 320 до 1024 КБ в зависимости от версии Java и используемой системы. Для 64-битной программы Java 8 с минимальным использованием стека максимальное количество вложенных вызовов методов составляет около 7 000. Как правило, нам не нужно больше, за исключением очень специфических случаев. Одним из таких случаев являются рекурсивные вызовы методов.
Исключение Tail Call (TCE) Представление среды в стеке представляется необходимым для возобновления вычислений после возврата вызываемого метода. Но не всегда. Когда вызов метода является последним, что нужно сделать в вызывающем методе, возобновлять его нечего, когда он возвращается, поэтому все должно быть в порядке, чтобы продолжить непосредственно с вызывающей стороной текущего метода вместо самого текущего метода. Вызов метода, происходящий в последней позиции, что означает последнее, что нужно сделать перед возвратом, называется tail call . Предотвращение передачи среды в стек для возобновления обработки метода после хвостового вызова — это метод оптимизации, известный как устранение хвостового вызова (TCE). К сожалению, Java не поддерживает TCE.
Устранение Tail Call иногда называют Оптимизацией Tail Call (TCO). TCE — это, как правило, оптимизация, и мы можем жить без нее. Однако, когда речь идет о рекурсивных вызовах функций, TCE больше не является оптимизацией. Это обязательная функция. Вот почему TCE — лучший термин, чем TCO, когда речь идет об обработке рекурсии.
Хвостовые рекурсивные методы и функции
Большинство функциональных языков реализуют ТВК. Однако TCE недостаточно, чтобы сделать возможным каждый рекурсивный вызов. Чтобы быть кандидатом в TCE, рекурсивный вызов должен быть последним, что должен сделать метод. Подумайте о следующем методе, вычисляющем сумму элементов списка:
|
1
2
3
4
5
|
static Integer sum(List<Integer> list) { return list.isEmpty() ? 0 : head(list) + sum(tail(list));} |
Этот метод использует методы head() и tail() . Обратите внимание, что рекурсивный вызов метода sum — это не последнее, что должен делать метод. Четыре последние вещи, которые делает метод:
- вызов метода
head - вызов метода
tail - вызов метода
sum - добавление результата
headи результатаsum
Даже если бы у нас был TCE, мы не смогли бы использовать этот метод со списками из 10 000 элементов, потому что рекурсивный вызов не находится в хвостовой позиции. Тем не менее, этот метод может быть переписан для того, чтобы перевести вызов sum в хвостовую позицию:
|
1
2
3
4
5
6
7
8
9
|
static Integer sum_(List<Integer> list) { return sumTail(list, 0);} static Integer sumTail(List<Integer> list, int acc) { return list.isEmpty() ? acc : sumTail(tail(list), acc + head(list));} |
Теперь метод sumTail является хвостовой sumTail и может быть оптимизирован с помощью TCE.
Абстракция рекурсии
Пока все хорошо, но зачем все это, поскольку Java не поддерживает TCE? Хорошо, Java не реализует это, но мы можем обойтись без этого. Все, что нам нужно сделать, это:
- Представление неоцененных вызовов методов
- Хранение их в стекоподобной структуре, пока мы не встретим терминальное условие
- Оценка звонков в порядке LIFO
В большинстве примеров рекурсивных методов в качестве примера используется функция Factorial. Другие используют пример ряда Фибоначчи. Чтобы начать наше исследование, мы будем использовать гораздо более простой метод рекурсивного сложения.
Обе рекурсивные и corecursive функции — это функции, где f(n) представляет собой композицию из f(n‑1) , f(n‑2) , f(n‑3) и т. Д., Пока не встретится терминальное условие (обычно f(0) из f(1) ). Помните, что в традиционном программировании составление обычно означает составление результатов оценки. Это означает, что составление функций f(a) и g(a) состоит из вычисления g(a) последующим использованием результата в качестве входных данных для f . Это не должно быть сделано таким образом. Вы можете разработать метод compose для компоновки функций, а функцию higherCompose для того же. Ни один из этих методов или эта функция не будет оценивать составные функции. Они будут производить только другую функцию, которая может быть применена позже.
Рекурсия и corecursion похожи, хотя и с разницей. Мы создаем список вызовов функций вместо списка функций. В corecursion каждый шаг является терминальным, поэтому его можно оценить, чтобы получить результат и использовать его в качестве входных данных для следующего шага. С рекурсией мы начинаем с другого конца. Таким образом, мы должны помещать не оцененные вызовы в список, пока не найдем условие терминала, из которого мы можем обработать список в обратном порядке. Другими словами, мы складываем шаги (не оценивая их) до тех пор, пока не будет найден последний, а затем обрабатываем стек в обратном порядке (последний пришел первым вышел), оценивая каждый шаг и используя результат в качестве входных данных для следующего ( на самом деле предыдущий) один.
У нас проблема в том, что для этого Java использует стек потоков, а его возможности очень ограничены. Как правило, стек переполняется после 6000-7000 шагов.
Что нам нужно сделать, это создать функцию или метод, возвращающий необработанный шаг. Чтобы представить шаг в вычислении, мы будем использовать абстрактный класс с именем TailCall (поскольку мы хотим представить вызов метода, который появляется в хвостовой позиции).
Этот абстрактный класс TailCall будет иметь два подкласса: один будет представлять промежуточный вызов, когда обработка одного шага приостанавливается для вызова нового метода для оценки следующего шага. Это будет представлено классом с именем Suspend . Он будет создан с помощью Supplier<TailCall>> , который будет представлять следующий рекурсивный вызов. Таким образом, вместо того, чтобы помещать все TailCalls в список, мы TailCalls связанный список, связывая каждый хвостовой вызов со следующим. Преимущество этого подхода состоит в том, что такой связанный список фактически является стеком, предлагающим вставку с постоянным временем, а также доступ с постоянным временем к последнему вставленному элементу, что является оптимальным для структуры LIFO.
Вторая реализация будет представлять последний вызов, который должен вернуть результат. Итак, мы назовем это Return . Он не будет содержать ссылку на следующий TailCall , так как больше ничего нет, но он будет содержать результат. Вот что мы получаем:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import java.util.function.Supplier;public abstract class TailCall<T> { public static class Return<T> extends TailCall<T> { private final T t; public Return(T t) { this.t = t; } } public static class Suspend<T> extends TailCall<T> { private final Supplier<TailCall<T>> resume; private Suspend(Supplier<TailCall<T>> resume) { this.resume = resume; } }} |
Для обработки этих классов нам понадобятся некоторые методы: один для возврата результата, один для возврата следующего вызова и один вспомогательный метод для определения, является ли TailCall Suspend или Return . Мы могли бы избежать этого последнего метода, но нам пришлось бы использовать instanceof для выполнения работы, что некрасиво. Три метода будут:
|
1
2
3
4
5
|
public abstract TailCall<T> resume();public abstract T eval();public abstract boolean isSuspend(); |
Метод resume не будет иметь реализации в Return и просто выдаст исключение времени выполнения. Пользователь нашего API не должен быть в состоянии вызвать этот метод, поэтому, если он в конечном итоге вызывается, это будет ошибкой, и мы остановим приложение. В классе Suspend он вернет следующий TailCall .
Метод eval вернет результат, сохраненный в классе Return . В нашей первой версии он вызовет исключение времени выполнения при вызове в классе Suspend .
Метод isSuspend просто возвращает true в Suspend и false в Return . В листинге 1 показана эта первая версия.
Листинг 1. Абстрактный класс TailCall и его два подкласса
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
import java.util.function.Supplier;public abstract class TailCall<T> { public abstract TailCall<T> resume(); public abstract T eval(); public abstract boolean isSuspend(); public static class Return<T> extends TailCall<T> { private final T t; public Return(T t) { this.t = t; } @Override public T eval() { return t; } @Override public boolean isSuspend() { return false; } @Override public TailCall<T> resume() { throw new IllegalStateException("Return has no resume"); } } public static class Suspend<T> extends TailCall<T> { private final Supplier<TailCall<T>> resume; public Suspend(Supplier<TailCall<T>> resume) { this.resume = resume; } @Override public T eval() { throw new IllegalStateException("Suspend has no value"); } @Override public boolean isSuspend() { return true; } @Override public TailCall<T> resume() { return resume.get(); } }} |
Теперь, чтобы добавить рекурсивный метод к работе с любым количеством шагов (в пределах доступного объема памяти!), Нам нужно внести небольшие изменения. Начиная с нашего оригинального метода:
|
1
2
3
4
5
|
static int add(int x, int y) { return y == 0 ? x : add(++x, --y) ;} |
Нам просто нужно внести изменения, показанные в листинге 2.
Листинг 2: Модифицированный рекурсивный метод
|
1
2
3
4
5
|
static TailCall<Integer> add(int x, int y) { // #1 return y == 0 ? new TailCall.Return<>(x) // #2 : new TailCall.Suspend<>(() -> add(x + 1, y – 1)); // #3} |
- # 1 метод теперь возвращает TailCall
- # 2 В терминальном состоянии, возврат возвращается
- # 3 В нетерминальном состоянии возвращается Suspend
Наш метод теперь возвращает TailCall<Integer> вместо int (# 1). Это возвращаемое значение может быть Return<Integer> (# 2), если мы достигли состояния терминала, или Suspend<Integer> (# 3), если мы еще этого не сделали. Возврат создается с результатом вычисления (который равен x, поскольку y равно 0), а Suspend создается с помощью Supplier<TailCall<Integer>> , который является следующим шагом вычисления с точки зрения последовательности выполнения, или предыдущий с точки зрения последовательности вызова. Очень важно понимать, что Return соответствует последнему шагу с точки зрения вызова метода, но первому шагу с точки зрения оценки. Также обратите внимание, что мы немного изменили оценку, заменив ++x и --y на x + 1 и y – 1 . Это было необходимо, потому что мы используем замыкание, которое работает, только если закрытые переменные являются окончательными. Это обман, но не так сильно. Мы могли бы создать и вызвать два метода dec и inc, используя оригинальные операторы.
Этот метод возвращает цепочку экземпляров TailCall, все из которых являются экземплярами Suspend, кроме последнего, который является Return.
Пока все хорошо, но, очевидно, этот метод не является заменой оригинальному. Не ахти какое дело! Оригинальный метод был использован как:
|
1
|
System.out.println(add(x, y)) |
Мы можем использовать наш новый метод следующим образом:
|
1
2
3
4
5
6
7
8
9
|
TailCall<Integer> tailCall = add(3, 100000000);while(tailCall .isSuspend()) {tailCall = tailCall.resume();}System.out.println(tailCall.eval()); |
Разве это не выглядит красиво? Ну, если вы чувствуете себя несколько разочарованным, я могу понять. Вы думали, что мы просто будем использовать новый метод вместо старого, прозрачным способом. Кажется, мы далеки от этого. Но мы можем сделать вещи намного лучше с небольшими усилиями.
Снижение замены для рекурсивных методов стековой базы
В начале предыдущего раздела мы говорили, что пользователь нашего рекурсивного API не будет иметь возможности связываться с экземплярами TailCall, вызывая возобновление на Return или eval на Suspend. Этого легко достичь, поместив код оценки в метод eval класса Suspend:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
public static class Suspend<T> extends TailCall<T> { ... @Override public T eval() { TailCall<T> tailRec = this; while(tailRec.isSuspend()) { tailRec = tailRec.resume(); } return tailRec.eval(); } |
Теперь мы можем получить результат рекурсивного вызова намного проще и безопаснее:
|
1
|
add(3, 100000000).eval() |
Но это еще не то, что мы хотим. Мы хотим избавиться от этого вызова метода eval. Это можно сделать с помощью вспомогательного метода:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
|
import static com.fpinjava.excerpt.TailCall.ret;import static com.fpinjava.excerpt.TailCall.sus;. . .public static int add(int x, int y) { return addRec(x, y).eval();}private static TailCall<Integer> addRec(int x, int y) { return y == 0 ? ret(x) : sus(() -> addRec(x + 1, y - 1));} |
Теперь мы можем вызвать метод add точно так же, как и исходный. Обратите внимание, что мы упростили использование нашего рекурсивного API, предоставив статические фабричные методы для создания экземпляров Return и Suspend:
|
1
2
3
4
5
6
7
|
public static <T> Return<T> ret(T t) { return new Return<>(t);}public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) { return new Suspend<>(s);} |
В листинге 3 показан полный класс TailCall. Мы добавили приватный конструктор no arg для предотвращения расширения другими классами.
Листинг 3: Полный класс TailCall
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
package com.fpinjava.excerpt;import java.util.function.Supplier;public abstract class TailCall<T> { public abstract TailCall<T> resume(); public abstract T eval(); public abstract boolean isSuspend(); private TailCall() {} public static class Return<T> extends TailCall<T> { private final T t; private Return(T t) { this.t = t; } @Override public T eval() { return t; } @Override public boolean isSuspend() { return false; } @Override public TailCall<T> resume() { throw new IllegalStateException("Return has no resume"); } }public static class Suspend<T> extends TailCall<T> { private final Supplier<TailCall<T>> resume; private Suspend(Supplier<TailCall<T>> resume) { this.resume = resume; } @Override public T eval() { TailCall<T> tailRec = this; while(tailRec.isSuspend()) { tailRec = tailRec.resume(); } return tailRec.eval(); } @Override public boolean isSuspend() { return true; } @Override public TailCall<T> resume() { return resume.get(); } } public static <T> Return<T> ret(T t) { return new Return<>(t); } public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) { return new Suspend<>(s); }} |
Теперь, когда у вас есть безопасный для стека хвостовой рекурсивный метод, можете ли вы сделать то же самое с функцией? В моей книге « Функциональное программирование на Java» я говорю о том, как это сделать.