Вообще говоря, рекурсия — это концепция четко определенной самоссылки. Это определение последовательности элементов путем обработки одного или нескольких предшествующих элементов в соответствии с правилом или формулой, включающей конечное число шагов.

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

Например, возьмем эту функцию:

`float _pow_recursion(float x, float y)
{
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);

return (_pow_recursion(x, y - 1) * x);
}`

В этом нашем базовом условии здесь if (y == 0),, если это условие выполнено, цикл остановится.

Это условие необходимо, потому что при его отсутствии мы будем вызывать нашу функцию бесконечно.

Теперь к циклической части, когда мы вызываем эту функцию в

return (_pow_recursion(x, y - 1) * x);

мы делаем это с поворотом, мы будем увеличивать или уменьшать y на 1, чтобы достичь 0 и, таким образом, приблизиться к нашему базовому условию (y == 0).

это больше всего похоже на русских кукол, каждая кукла держит внутри такую ​​же, но меньшую куклу (у — 1 в нашем случае).

Но, наконец, когда мы выполняем наше условие, что происходит, ну, мы возвращаем значение, конечно, какое значение точно хорошо, когда вы == 0 достигается, мы возвращаем 1, это значение затем добавляется к предыдущему возвращению, ведьма разделит его на x и отправит его к более высокой функции, пока мы не достигнем первого экземпляра, который мы назвали функцией.

Таким образом, если функция or повторяется пять раз, окончательный результат будет примерно таким ( ( ( ( (1 / x) / x) / x) / x), сложенным аналогично куклам внутри друг друга.

Еще примеры рекурсии:

  • Русские матрешки. Каждая кукла сделана из цельного дерева или полая и содержит внутри еще одну матрешку.
  • Современная ОС определяет каталоги файловой системы рекурсивным способом. Файловая система состоит из каталога верхнего уровня, а содержимое этого каталога состоит из файлов и других каталогов.
  • Большая часть синтаксиса в современных языках программирования определяется рекурсивным способом. Например, список аргументов состоит из (1) аргумента или (2) списка аргументов, за которыми следует запятая и аргумент.

Практика: дайте рекурсивное определение следующих структур данных:

  • Связанный список
  • Количество узлов в связанном списке

Определение проблем способами, облегчающими рекурсию

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

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

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

Пример 1. Факторный расчет

Мы знаем, что факториал n (n ›= 0) вычисляется как n! = n * (n-1) * (n-2) * … * 2 * 1. Обратите внимание, что произведение (n-1) * (n-2) * … * 2 * 1 равно (n-1)!. Таким образом, мы можем записать выражение как n! = n * (n-1)!, что является рекурсивным выражением вычисления факториала.

Что такое базовый случай? Что такое рекурсивный шаг?

public class RecursiveFactorial {
public static void main (String[] args) {
for (int i = 1; i ‹ 10; i++)
System.out.println(i + “\t” + factorial(i ));
}
static int factorial (int n) {
if (n ‹ 2) return 1; // базовый случай
else return n * factorial(n-1); // рекурсивный регистр
}
}

Приведенная выше рекурсия называется линейной рекурсией, так как она выполняет один рекурсивный вызов за раз. Эквивалент цикла:

public static int factorial(int n) {
int result = 1;
for (int i = 2; i ‹= n ; i++)
результат *= i;
вернуть результат;
}

Рекурсия и стеки

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

  • На этапе пересылки значения локальных переменных и параметров, а также адрес возврата помещаются в стек для каждого уровня рекурсии.
  • На этапе отката адрес из стека извлекается и используется для возврата к выполнению остальной части кода на вызывающем уровне, а локальные переменные и параметры из стека извлекаются и используются для восстановления состояния этого вызова.

Упражнение

  • Возведение в степень. Вычислите xn, используя как итерацию, так и рекурсию. (Предположим, что x › 0 и n ›= 0)

Пример 2. Реверсирование массива

Рассмотрим задачу обращения n элементов массива A таким образом, чтобы первый элемент становился последним, второй элемент становился предпоследним и так далее. Мы можем решить эту проблему, используя линейную рекурсию, заметив, что обращение массива может быть достигнуто путем замены местами первого и последнего элементов, а затем рекурсивного обращения оставшихся элементов в массиве.

Алгоритм ReverseArray(A, i, j):
Ввод: массив A и неотрицательное целое число индексы i и j
Вывод: перестановка элементов в A, начиная с индекса i и заканчивается на j
if i ‹ j то
Поменять местами A[i] и A[j]
ReverseArray(A, i+1, j-1)
возврат

Упражнения

  • Суммирование элементов массива рекурсивно
  • Поиск максимального элемента в массиве A из n элементов с использованием рекурсии

Пример 3. Ханойские башни

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

В головоломке Ханойские башни нам дается платформа с тремя колышками, a, b и c, торчащими из нее. На колышке a находится стопка из n дисков, каждый из которых больше предыдущего, так что самый маленький находится вверху, а самый большой — внизу. Задача состоит в том, чтобы переместить все диски с привязки a на c, перемещая по одному диску за раз, чтобы никогда не класть больший диск поверх меньшего. На следующих рисунках приведены примеры начального положения и конечного положения дисков при n = 4. Рассмотрим пример перемещения 4 дисков.

a b c a b c
(источник) (запас) (назначение) (источник) (запас) (назначение)

Подумайте, что является базовым случаем? Что такое рекурсивный шаг?

На верхнем уровне мы хотим переместить 4 диска из привязки a в c с запасной привязкой b. Мы можем разбить задачу перемещения 4 дисков на три шага:

  1. Переместите диск 3 и меньше с колышка a на b, используя c в качестве запасного стержня. Это можно сделать, рекурсивно вызвав ту же процедуру, но вместо этого с 3 дисками. После этой процедуры у нас будет 3 меньших диска на привязке b.
  2. Переместите диск 4 со штифта a на штифт c. После этой процедуры у нас будет 3 меньших диска на привязке b, диск 4 на привязке c и привязка a пуста.
  3. Переместите диск 3 и меньше со штифта b на c, используя a в качестве запасного штифта. Опять же, это можно сделать, рекурсивно вызвав одну и ту же процедуру на 3-х дисках с разными источником и местом назначения. После этой процедуры у нас будут все диски на привязке c без нарушения правил.

Псевдокод выглядит следующим образом. Мы вызываем эту функцию, чтобы переместить 4 диска с помощью MoveDisk(4, a, c, b).

Алгоритм MoveDisk(диск, источник, назначение, запасной) {
если (диск = = 1) то
переместите диск из источника в назначение
иначе
MoveDisk(диск-1, источник, резервный, целевой) // шаг 1 выше
перемещение диска из исходного в целевой // шаг 2 выше
MoveDisk(диск-1, запасной, назначение, источник) // шаг 3 выше
}

Проследим наше решение. Чтобы визуализировать рекурсивный процесс вызова, мы создаем дерево вызовов. Это дерево вызовов для перемещения 3 дисков из привязки a в c.

Обратите внимание, что каждый вызов MoveDisk будет разветвляться на вызовы двух функций, если только это не базовый случай. Если мы хотим переместить n дисков, сколько перемещений нам потребуется с помощью этой рекурсивной функции?

Предположим, что M(i) представляет количество перемещений дисков. Давайте посчитаем, сколько времени потребуется, чтобы переместить n дисков.

  • M(1) = 1
  • M(2) = 2M(1) + 1 = 3
  • M(3) = 2M(2) + 1 = 7
  • M(4) = 2M(3) + 1 = 15
  • …
  • Мы можем предположить, что M(n) = 2n — 1

В этом можно убедиться, подключив его к нашей функции.

  • M(1) = 21–1
  • M(n) = 2M(n-1) + 1 = 2[2M(n-2) + 1] + 1 = … = 2k M(n-k) + 2k-1 + 2k-2 + … + 2 + 1
  • M(n) = 2n — 1, когда k = n-1 (останавливаясь на базовом случае)

64-дисковая версия головоломки находится в ханойском монастыре, где монахи постоянно работают над решением головоломки. Когда они закончат головоломку, миру придет конец. Теперь вы знаете ответ. Как долго будет существовать мир? примерно 585,442 миллиарда лет. В настоящее время Вселенной около 13,7 миллиардов лет.

Пример 4. Последовательность Фибоначчи

Последовательность Фибоначчи — это последовательность чисел 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …. Первые два числа последовательности равны 1, а каждое последующее число является суммой двух предшествующих чисел. Мы можем определить функцию F(n), которая вычисляет n-е число Фибоначчи.

Во-первых, базовые случаи: F(0) = 1 и F(1) = 1.

Теперь рекурсивный случай: F(n) = F(n-1) + F(n-2).

Напишите рекурсивную функцию и дерево вызовов для F(5).

Алгоритм Fib(n) {
if (n ‹ 2) возврат 1
иначе возврат Фибоначчи (n-1) + Фибоначчи (n-2)
}

Приведенная выше рекурсия называется бинарной рекурсией, поскольку она делает два рекурсивных вызова вместо одного. Сколько вызовов требуется для вычисления k-го числа Фибоначчи? Пусть nk обозначает количество вызовов, выполненных при выполнении.

  • n0 = 1
  • n1 = 1
  • n2 = n1 + n0 + 1 = 3 > 21
  • n3 = n2 + n1 + 1 = 5 > 22
  • n4 = n3 + n2 + 1 = 9 > 23
  • n5 = n4 + n3 + 1 = 15 > 23
  • …
  • nk > 2k/2

Это означает, что рекурсия Фибоначчи делает количество вызовов, экспоненциальное по k. Другими словами, использование двоичной рекурсии для вычисления чисел Фибоначчи очень неэффективно. Сравните эту проблему с бинарным поиском, который очень эффективен при поиске элементов, почему эта бинарная рекурсия неэффективна? Основная проблема с описанным выше подходом заключается в том, что существует несколько перекрывающихся рекурсивных вызовов.

Мы можем вычислить F(n) намного эффективнее, используя линейную рекурсию. Один из способов выполнить это преобразование — определить рекурсивную функцию, которая вычисляет пару последовательных чисел Фибоначчи F(n) и F(n-1), используя соглашение F( -1) = 0.

Алгоритм LinearFib(n) {
Входные данные: неотрицательное целое число n
Выход: пара чисел Фибоначчи (Fn, Fn-1)
if ( n ‹= 1) затем
возврат (n, 0)
else
(i, j) ← LinearFib(n-1)
возврат (i + j, i)
}

Поскольку каждый рекурсивный вызов LinearFib уменьшает аргумент n на 1, первоначальный вызов приводит к серии из n-1 дополнительных вызовов. Эта производительность значительно быстрее, чем экспоненциальное время, необходимое для двоичной рекурсии. Поэтому при использовании бинарной рекурсии мы должны сначала попытаться полностью разбить задачу на две части или, мы должны быть уверены, что перекрывающиеся рекурсивные вызовы действительно необходимы. Обычно мы можем устранить перекрывающиеся рекурсивные вызовы, используя больше памяти для отслеживания предыдущих значений. На самом деле этот подход является центральной частью метода, называемого динамическое программирование. Давайте используем итерацию для генерации чисел Фибоначчи. В чем сложность этого алгоритма?

public static int IterationFib(int n) {
if (n ‹ 2) return n;
int f0 = 0, f1 = 1, f2 = 1;
for (int i = 2; i ‹ n; i++) {
f0 = f1;< br /> f1 = f2;
f2 = f0 + f1;
}
return f2;
}

Пример 5. Бинарный поиск

Каков базовый случай? Что такое рекурсивный случай?

открытый класс TestBinarySearch {
TestBinarySearch() {
int[] arr = {22, 33, 44, 55, 66, 77, 88, 99};
System.out.println(“ search(" + 55 + "): " + BinarySearch(arr, 0, arr.length-1, 55));
System.out.println("search(" + 50 +"): " + BinarySearch (arr, 0, arr.length-1, 50));
}

public static void main(String[] args) {
new TestBinarySearch();
}

int BinarySearch(int[] arr, int start, int end, int x) {
int mid = (start + end) / 2;
if (arr[mid] = = x) return mid;
if (start › end) return -1;
if (arr[mid] ‹ x) return BinarySearch(arr, mid+1, end, x);
else return BinarySearch(arr , начало, середина-1, х);
}
}

Упражнение

  • Суммирование элементов массива с помощью двоичной рекурсии

Недостатки рекурсии

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

Рекурсия может выполнять избыточные вычисления. Рассмотрим рекурсивное вычисление последовательности Фибоначчи.

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

Хвостовая рекурсия

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