# Recursion
Recursion occurs when a method calls itself. Such a method is called recursive. A recursive method may be more concise than an equivalent non-recursive approach. However, for deep recursion, sometimes an iterative solution can consume less of a thread’s finite stack space.
This topic includes examples of recursion in Java.
# Deep recursion is problematic in Java
Consider the following naive method for adding two positive numbers using recursion:
This is algorithmically correct, but it has a major problem. If you call add with a large a , it will crash with a StackOverflowError , on any version of Java up to (at least) Java 9.
In a typical functional programming language (and many other languages) the compiler optimizes tail recursion
(opens new window) . The compiler would notice that the call to add (at the tagged line) is a tail call
(opens new window) , and would effectively rewrite the recursion as a loop. This transformation is called tail-call elimination.
However, current generation Java compilers do not perform tail call elimination. (This is not a simple oversight. There are substantial technical reasons for this; see below.) Instead, each recursive call of add causes a new frame to be allocated on the thread’s stack. For example, if you call add(1000, 1) , it will take 1000 recursive calls to arrive at the answer 1001 .
The problem is that the size of Java thread stack is fixed when the thread is created. (This includes the "main" thread in a single-threaded program.) If too many stack frames are allocated the stack will overflow. The JVM will detect this and throw a StackOverflowError .
One approach to dealing with this is to simply use a bigger stack. There are JVM options that control the default size of a stack, and you can also specify the stack size as a Thread constructor parameter. Unfortunately, this only "puts off" the stack overflow. If you need to do a computation that requires an even larger stack, then the StackOverflowError comes back.
The real solution is to identify recursive algorithms where deep recursion is likely, and manually perform the tail-call optimization at the source code level. For example, our add method can be rewritten as follows:
(Obviously, there are better ways to add two integers. The above is simply to illustrate the effect of manual tail-call elimination.)
# Why tail-call elimination is not implemented in Java (yet)
There are a number of reasons why adding tail call elimination to Java is not easy. For example:
- Some code could rely on StackOverflowError to (for example) place a bound on the size of a computational problem.
- Sandbox security managers often rely on analyzing the call stack when deciding whether to allow non-privileged code to perform a privileged action.
"The effects of removing the caller’s stack frame are visible to some APIs, notably access control checks and stack tracing. It is as if the caller’s caller had directly called the callee. Any privileges possessed by the caller are discarded after control is transferred to the callee. However, the linkage and accessibility of the callee method are computed before the transfer of control, and take into account the tail-calling caller."
In other words, tail-call elimination could cause an access control method to mistakenly think that a security sensitive API was was being called by trusted code.
# The basic idea of recursion
What is recursion:
In general, recursion is when a function invokes itself, either directly or indirectly. For example:
Conditions for applying recursion to a problem:
There are two preconditions for using recursive functions to solving a specific problem:
In Java there is a third precondition: it should not be necessary to recurse too deeply to solve the problem; see Deep recursion is problematic in Java
Example
The following function calculates factorials using recursion. Notice how the method factorial calls itself within the function. Each time it calls itself, it reduces the parameter n by 1. When n reaches 1 (the base condition) the function will recurse no deeper.
This is not a practical way of computing factorials in Java, since it does not take account of integer overflow, or call stack overflow (i.e. StackOverflowError exceptions) for large values of n .
# Types of Recursion
Recursion can be categorized as either Head Recursion or Tail Recursion, depending on where the recursive method call is placed.
In head recursion, the recursive call, when it happens, comes before other processing in the function (think of it happening at the top, or head, of the function).
In tail recursion, it’s the opposite—the processing occurs before the recursive call. Choosing between the two recursive styles may seem arbitrary, but the choice can make all the difference.
A function with a path with a single recursive call at the beginning of the path uses what is called head recursion. The factorial function of a previous exhibit uses head recursion. The first thing it does once it determines that recursion is needed is to call itself with the decremented parameter. A function with a single recursive call at the end of a path is using tail recursion.
If the recursive call occurs at the end of a method, it is called a tail recursion . The tail recursion is similar to a loop . The method executes all the statements before jumping into the next recursive call .
If the recursive call occurs at the beginning of a method, it is called a head recursion . The method saves the state before jumping into the next recursive call .
# Computing the Nth Fibonacci Number
The following method computes the Nth Fibonacci number using recursion.
The method implements a base case (n <= 2) and a recursive case (n>2). This illustrates the use of recursion to compute a recursive relation.
However, while this example is illustrative, it is also inefficient: each single instance of the method will call the function itself twice, leading to an exponential growth in the number of times the function is called as N increases. The above function is O(2 N ), but an equivalent iterative solution has complexity O(N). In addition, there is a "closed form" expression that can be evaluated in O(N) floating-point multiplications.
# Computing the Nth power of a number
The following method computes the value of num raised to the power of exp using recursion:
This illustrates the principles mentioned above: the recursive method implements a base case (two cases, n = 0 and n = 1) that terminates the recursion, and a recursive case that calls the method again. This method is O(N) and can be reduced to a simple loop using tail-call optimization.
# Traversing a Tree data structure with recursion
Consider the Node class having 3 members data, left child pointer and right child pointer like below.
We can traverse the tree constructed by connecting multiple Node class’s object like below, the traversal is called in-order traversal of tree.
As demonstrated above, using recursion we can traverse the tree data structure without using any other data structure which is not possible with the iterative approach.
# StackOverflowError & recursion to loop
If a recursive call goes "too deep", this results in a StackOverflowError . Java allocates a new frame for every method call on its thread’s stack. However, the space of each thread’s stack is limited. Too many frames on the stack leads to the Stack Overflow (SO).
# Example
Calling this method with large parameters (e.g. recursion(50000) probably will result in a stack overflow. The exact value depends on the thread stack size, which in turn depends on the thread construction, command-line parameters such as -Xss , or the default size for the JVM.
# Workaround
A recursion can be converted to a loop by storing the data for each recursive call in a data structure. This data structure can be stored on the heap rather than on the thread stack.
In general the data required to restore the state of a method invocation can be stored in a stack and a while loop can be used to "simulate" the recursive calls. Data that may be required include:
- the object the method was called for (instance methods only)
- the method parameters
- local variables
- the current position in the execution or the method
# Example
The following class allows recursive of a tree structure printing up to a specified depth.
Java Language
Рекурсия
Рекурсия происходит, когда метод вызывает себя. Такой метод называется рекурсивным . Рекурсивный метод может быть более кратким, чем эквивалентный нерекурсивный подход. Однако для глубокой рекурсии иногда итерационное решение может потреблять меньше пространства стека в потоке.
В этом разделе приведены примеры рекурсии на Java.
замечания
Проектирование рекурсивного метода
При разработке рекурсивного метода помните, что вам нужно:
Базовый вариант. Это определит, когда ваша рекурсия остановится и выведет результат. Базовый случай в факториальном примере:
Рекурсивный вызов. В этом заявлении вы повторно вызываете метод с измененным параметром. Рекурсивный вызов в приведенном выше факториальном примере:
Выход
В этом примере вы вычисляете n-й факторный номер. Первыми факториалами являются:
0! = 1
1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 6
4! = 1 x 2 x 3 x 4 = 24
.
Удаление Java и Tail-call
Текущие компиляторы Java (вплоть до Java 9) не выполняют исключение хвостового вызова. Это может повлиять на производительность рекурсивных алгоритмов, и если рекурсия достаточно глубокая, это может привести к сбоям StackOverflowError ; см. Глубокая рекурсия проблематична в Java
Основная идея рекурсии
Что такое рекурсия:
В общем, рекурсия — это когда функция вызывает себя, прямо или косвенно. Например:
Условия применения рекурсии к задаче:
Существуют две предпосылки для использования рекурсивных функций для решения конкретной проблемы:
Должно быть базовое условие проблемы, которое будет конечной точкой для рекурсии. Когда рекурсивная функция достигает базового условия, она не делает дальнейших (более глубоких) рекурсивных вызовов.
Каждый уровень рекурсии должен пытаться решить меньшую проблему. Таким образом, рекурсивная функция делит проблему на более мелкие и мелкие части. Предполагая, что проблема конечна, это обеспечит завершение рекурсии.
В Java есть третье предварительное условие: не нужно слишком глубоко задумываться о решении проблемы; см. Глубокая рекурсия проблематична в Java
пример
Следующая функция вычисляет факториалы с использованием рекурсии. Обратите внимание, как метод factorial вызывает себя внутри функции. Каждый раз, когда он называет себя, он уменьшает параметр n на 1. Когда n достигает 1 (базовое условие), функция не будет углубляться.
Это не практический способ вычисления факториалов в Java, поскольку он не учитывает переполнение целого числа или переполнение стека вызовов (например, исключения StackOverflowError ) при больших значениях n .
Вычисление N-го числа Фибоначчи
Следующий метод вычисляет N-й номер Фибоначчи с использованием рекурсии.
Метод реализует базовый случай (n <= 2) и рекурсивный случай (n> 2). Это иллюстрирует использование рекурсии для вычисления рекурсивного отношения.
Однако, хотя этот пример является иллюстративным, он также неэффективен: каждый отдельный экземпляр метода дважды вызовет эту функцию, что приведет к экспоненциальному росту числа раз, когда функция называется ростом N. Вышеуказанная функция O (2 N ), но эквивалентное итерационное решение имеет сложность O (N). Кроме того, существует выражение «закрытая форма», которое может быть оценено с помощью умножения с плавающей запятой O (N).
Вычисление суммы целых чисел от 1 до N
Следующий метод вычисляет сумму целых чисел от 0 до N, используя рекурсию.
Этот метод O (N) и может быть сведен к простому циклу с использованием оптимизации хвостового вызова. На самом деле существует замкнутое выражение формы, которое вычисляет сумму в операциях O(1) .
Вычисление N-й степени числа
Следующий метод вычисляет значение num увеличенное до степени exp используя рекурсию:
Это иллюстрирует принципы, упомянутые выше: рекурсивный метод реализует базовый случай (два случая, n = 0 и n = 1), который завершает рекурсию, и рекурсивный случай, который вызывает метод снова. Этот метод O (N) и может быть сведен к простому циклу с использованием оптимизации хвостового вызова.
Обратить строку с помощью рекурсии
Ниже приведен рекурсивный код для изменения строки
Перемещение структуры данных дерева с рекурсией
Рассмотрим класс Node, содержащий 3 элемента данных, левый указатель на ребенка и правый дочерний указатель, как показано ниже.
Мы можем пересечь дерево, построенное путем соединения нескольких объектов класса Node, как показано ниже, обход называется обходным деревом в порядке.
Как показано выше, используя рекурсию, мы можем пересечь структуру древовидных данных без использования какой-либо другой структуры данных, которая невозможна при итеративном подходе.
Типы рекурсии
Рекурсия может быть классифицирована как Head Recursion или Tail Recursion , в зависимости от места размещения рекурсивного метода.
При рекурсии головы рекурсивный вызов, когда это происходит, предшествует другой обработке в функции (думайте, что это происходит сверху или в голове функции).
В хвостовой рекурсии это противоположность — обработка происходит до рекурсивного вызова. Выбор между двумя рекурсивными стилями может показаться произвольным, но выбор может иметь значение.
Функция с путём с единственным рекурсивным вызовом в начале пути использует так называемую рекурсию головы. Факториальная функция предыдущего экспоната использует рекурсию головы. Первое, что он делает, когда оно определяет, что требуется рекурсия, — это вызвать себя с декрементированным параметром. Функция с единственным рекурсивным вызовом в конце пути использует хвостовую рекурсию.
Если рекурсивный вызов встречается в конце метода, он называется tail recursion . Рекурсия хвоста similar to a loop . method executes all the statements before jumping into the next recursive call .
Если рекурсивный вызов происходит в beginning of a method, it is called a head recursion . method saves the state before jumping into the next recursive call .
StackOverflowError & recursion to loop
Если рекурсивный вызов «слишком глубокий», это приводит к возникновению StackOverflowError . Java выделяет новый кадр для каждого вызова метода в стеке потока. Однако пространство стека каждого потока ограничено. Слишком много кадров в стеке приводит к переполнению стека (SO).
пример
Вызов этого метода с большими параметрами (например, recursion(50000) вероятно, приведет к переполнению стека. Точное значение зависит от размера стека потоков, что, в свою очередь, зависит от конструкции потока, параметров командной строки, таких как -Xss или размер по умолчанию для JVM.
Временное решение
Рекурсия может быть преобразована в цикл путем хранения данных для каждого рекурсивного вызова в структуре данных. Эта структура данных может храниться в куче, а не в стеке потоков.
В общем случае данные, необходимые для восстановления состояния вызова метода, могут храниться в стеке, а цикл while может использоваться для «имитации» рекурсивных вызовов. Данные, которые могут потребоваться, включают:
- объект, к которому был вызван метод (только методы экземпляра)
- параметры метода
- локальные переменные
- текущая позиция в исполнении или метод
пример
Следующий класс позволяет рекурсивно печатать древовидную структуру с заданной глубиной.
Это можно преобразовать в следующий цикл:
Примечание. Это всего лишь пример общего подхода. Часто вы можете найти гораздо лучший способ представления кадра и / или хранения данных кадра.
Глубокая рекурсия проблематична в Java
Рассмотрим следующий наивный метод для добавления двух положительных чисел с помощью рекурсии:
Это алгоритмически правильно, но это имеет серьезную проблему. Если вы вызовете add с большим a , он выйдет из строя с помощью StackOverflowError на любой версии Java до (по крайней мере) Java 9.
В типичном языке функционального программирования (и многих других языках) компилятор оптимизирует хвостовую рекурсию . Компилятор заметил бы, что вызов для add (в помеченной строке) является хвостовым вызовом и будет эффективно переписывать рекурсию как цикл. Это преобразование называется устранением хвостового вызова.
Однако компиляторы Java поколения текущего поколения не выполняют исключение хвостового вызова. (Это не простой надзор. Для этого существуют существенные технические причины, см. Ниже.) Вместо этого каждый рекурсивный вызов add вызывает выделение нового кадра в стеке потока. Например, если вы вызываете add(1000, 1) , для ответа 1001 потребуется 1000 рекурсивных вызовов.
Проблема в том, что размер потока потоков Java фиксируется при создании потока. (Сюда входит «основной» поток в однопоточной программе.) Если слишком много кадров стека распределены, стек будет переполняться. JVM обнаружит это и выбросит StackOverflowError .
Один из способов борьбы с этим — просто использовать больший стек. Есть JVM варианты , которые контролируют по умолчанию размера стека, и вы можете также указать размер стека в качестве Thread параметра конструктора. К сожалению, это только «отбрасывает» переполнение стека. Если вам нужно выполнить вычисления, для которых требуется еще больший стек, возвращается StackOverflowError .
Реальное решение состоит в том, чтобы идентифицировать рекурсивные алгоритмы, где вероятна глубокая рекурсия, и вручную выполнить оптимизацию хвостового вызова на уровне исходного кода. Например, наш метод add можно переписать следующим образом:
(Очевидно, что есть лучшие способы добавить два целых числа. Вышеупомянутое просто иллюстрирует эффект устранения ручного хвостового вызова.)
Почему исключение хвостового вызова не реализовано на Java (пока)
Существует ряд причин, по которым добавление исключения хвоста в Java нелегко. Например:
- Некоторый код может полагаться на StackOverflowError для (например) размещения привязки по размеру вычислительной проблемы.
- Менеджеры безопасности Sandbox часто полагаются на анализ стека вызовов при принятии решения о том, разрешать ли непривилегированный код выполнять привилегированное действие.
Как объясняет Джон Роуз в «Хвостах звонков на ВМ» :
«Эффекты удаления фрейма стека вызывающего абонента видны некоторым API-интерфейсам, особенно проверкам контроля доступа и трассировке стека. Как будто вызывающий вызывающий вызывал непосредственно вызываемый вызывающий. Любые привилегии, которыми обладает вызывающий, отбрасываются после того, как управление передано в Однако связь и доступность метода вызываемого метода вычисляются до передачи управления и учитывают вызывающего звонка вызывающего абонента ».
Другими словами, устранение хвостового вызова может привести к тому, что метод управления доступом ошибочно полагает, что защищенный от безопасности API был вызван доверенным кодом.
Что такое рекурсия java
Отдельно рассмотрим рекурсивные функции. Главное отличие рекурсивных функций от обычных методов состоит в том, что они рекурсивная функция может вызывать саму себя.
Например, рассмотрим функцию, которая вычисляет факториал числа:
Вначале проверяется условие: если вводимое число не равно 1, то мы умножаем данное число на результат этой же функции, в которую в качестве параметра передается число x-1. То есть происходит рекурсивный спуск. И так дальше, пока не дойдем того момента, когда значение параметра не будет равно единице.
Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и который помещается в начале функции. В случае с факториалом это if (x == 1) return 1; . И все рекурсивные вызовы должны обращаться к подфункциям, которые в конечном счете сходятся к базовому варианту. Так, при передаче в функцию положительного числа при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант.
Хотя в данном случае нужно отметить, что для определения факториала есть более оптимальные решения на основе циклов:
Еще одним распространенным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. В теории n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1.
Рекурсия в Java
Программирование и разработка
Рекурсивный подход очень подходит для тех задач, которые можно разбить на более мелкие, простые и повторяющиеся задачи. Это процедура, в которой функция вызывает себя многократно/рекурсивно, и должно быть хотя бы одно условие завершения/остановки, чтобы остановить рекурсию. Метод, который вызывает сам себя, описывается как рекурсивная функция, а весь процесс в Java известен как рекурсия.
Что такое рекурсия в Java?
Обычно мы наблюдаем, как функция вызывает какую-то другую функцию или функции. Однако рекурсивная функция многократно вызывает сама себя. Приведенные ниже фрагменты показывают, чем обычный метод отличается от рекурсивного.
Базовый синтаксис нормальной функции
publicvoidfirstFunction ( )
<
System . out . println ( «This is a normal Function» ) ;
secondFunction ( ) ;
>
Приведенный выше фрагмент показывает, как выглядит обычная определяемая пользователем функция, т. е. она имеет несколько операторов (кода) и вызывает функцию с именем secondFunction().
Базовый синтаксис рекурсивной функции
Теперь давайте посмотрим на приведенный ниже фрагмент, чтобы понять, как выглядит рекурсивная функция:
публичная недействительная первая функция ()
<
System . out . println ( «This is a Recursive Function» ) ;
firstFunction ( ) ;
>
Рассмотрим приведенный ниже рисунок, чтобы понять, как будет работать приведенная выше рекурсивная функция:
На приведенном выше рисунке показано, что функция постоянно вызывает сама себя, т. е. возникает сценарий бесконечного цикла. Теперь вам должно быть интересно, если функция постоянно вызывает себя, то как она остановится? Хорошо! Мы должны определить критерии завершения, чтобы остановить такую функцию в какой-то момент.
Условия остановки/завершения
На данный момент ясно, что должно быть условие, которое будет управлять потоком рекурсивной функции. С точки зрения программирования условие, которое останавливает вызов самой функции, называется условием остановки или базовым случаем.
Синтаксис рекурсивной функции с условием остановки будет выглядеть примерно так:
public void functionName ( )
<
functionName ( ) ;
//termination condition;
>
Состояние остановки может быть любым в зависимости от различных обстоятельств.
Примеры рекурсии Java
Этот раздел предоставит подробное понимание того, как рекурсивная функция работает с базовым случаем в Java.
Приведенный ниже фрагмент берет число от пользователя и находит факториал этого числа:
publicclassFactorialClass <
staticintfindFactorial ( int num ) <
if ( num == 0 ) <
return1 ;
>
else <
return ( num * findFactorial ( num — 1 ) ) ;
>
>
>
В приведенном выше фрагменте кода условие if-else используется для остановки рекурсии, когда «num» становится равным «0».
publicstaticvoidmain ( String [ ] args ) <
Scanner scan = new Scanner ( System . in ) ;
System . out . println ( «Enter a positive number:» ) ;
int number = scan. nextInt ( ) ;
if ( number < 0 ) <
System . out . println ( «You Entered an invalid number:» ) ;
> else <
int result = findFactorial ( number ) ;
System . out . println ( «Factorial : « + result ) ;
>
>
В основном методе мы получаем число от пользователя, проверяя, является ли число допустимым или нет, и, если число допустимо, вызываем метод findFactorial(). Весь код будет генерировать следующий вывод:
Вывод подтверждает, что рекурсивная функция работает правильно и правильно вычислила факториал 6.
Заключение
В Java процесс, в котором функция вызывает себя снова и снова, называется рекурсивной функцией/методом, а весь процесс известен как рекурсия. Базовый/остановочный случай должен быть определен в рекурсивных функциях, чтобы остановить рекурсию в какой-то момент, иначе функция никогда не остановится и вызовет себя неограниченное количество раз. В этой статье подробно рассматривается, что такое рекурсия, разница между обычной и рекурсивной функциями и как создавать рекурсивные функции в Java.