Рекурсия


В некоторых случаях нам нужно выполнять повторные вычисления.

И мы видели циклы for и while, которые выполняют повторные вычисления.

Теперь мы увидим гораздо более мощный механизм повторных вычислений, который называется рекурсией.

Ранее мы определили метод square, который, принимая целое число, возвращает квадрат числа.



Теперь мы хотели бы определить метод, который возводит в степень.

Мы хотим определить метод, который, учитывая базу x и показатель y, вычисляет x в степени y.



Поэтому, если y равно 2, мы вычисляем квадрат числа, как и раньше.

Вы видите, что в этом методе мы имеем два аргумента, целые числа x и y.

Давайте сначала попытаемся определить этот метод.

Давайте проанализируем несколько случаев.

Если y равно 0, то результат x равен степени 0, т. е. 1.

Если y равно 1, результат будет сразу x.

Если y равно 2, результатом является квадрат x.

Мы можем вызвать метод square, который мы определили ранее.

Если y равно 3, мы имеем x в кубе, предполагая, что у нас есть метод, называемый cube, определенный заранее.

И далее нам понадобятся другие методы для всех различных значений y, которые могут быть приняты.



Теперь мы можем заменить вызовы методов square, cube, и т. д. следующим кодом.

Таким образом, мы будем иметь x умножить на x, x умножить на x умножить на x и т. д.



Сейчас это немного лучше, но все же очень плохо, потому что порождает бесконечный код.

Но мы все же кое-чему научились.

Чтобы вычислить x в степени y, мы должны умножить x y раз.

Но мы должны учитывать, является ли эта процедура применима для всех целых чисел y?

Нет.

Только для y больше или равно 0.

Для отрицательного y нам понадобится другой способ умножения.

Если у нас есть повторное умножение, мы можем использовать цикл.



Вот пример того, как мы можем это сделать.

Мы инициализируем целочисленную переменную z в 1, а затем вводим цикл.

Счетчик i инициализируется 1 и увеличивается на 1 при каждом прогоне цикла.

Этот счетчик отслеживает, сколько х мы умножаем и накапливаем с помощью z.

И мы должны выполнять тело цикла ровно y раз, пока i не станет равен y.

Затем мы выходим и возвращаем накопленное значение в z.

Давайте проанализируем это снова.



x в степени y равно 1, если y равно 0.

А если y строго больше 0, то x в степени y равно x умножить на x в степени y минус 1.

Это то, что в математике называется рекуррентным уравнением.

И мы можем написать это на Java в виде вызова функции power.

Если y равно 0, возвращаем 1.



Иначе, возвращаем x умножить на вызов этой же функции с x и y минус 1.

Таким образом, тот же метод, который мы определили с помощью цикла, может быть определен с помощью рекурсии.

Оба эти способа эквивалентны.

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

Рекурсию можно сравнить с матрешкой.



Чтобы понять это вернемся к рекурсивному методу, который мы определили.

И давайте упростим последовательно вызов этого метода для небольшой степени, чтобы увидеть, что происходит.

Начнем с x в 3 степени.

Мы можем заменить вызов метода, используя определение метода.



Таким образом, мы пишем весь код метода, подставляя вместо y 3.

И в этой последовательности выражений мы переходим от вызова метода с параметрами (x, 3) к вызову метода с параметрами (x, 2).

Пишем весь код метода, подставляя вместо y 2.



И в этой последовательности выражений, мы перешли от вызова метода с параметрами (x, 2) к вызову метода с параметрами (x, 1).

И переходим к вызову метода с параметрами (x, 0).



x в степени 0 равно 1.



Теперь нам нужно собрать все вместе.

power (x, 3) равно x умножить на power (x, 2).



А power (x, 2) равно x умножить на power (x, 1).

А power (x, 1) равна x умножить на power (x, 0), что равно 1.

Таким образом, мы получаем x умножить на x умножить на x умножить на 1.

Так работает рекурсия – сначала мы спускаемся как по лестнице вниз, а затем поднимаемся опять наверх.

Это изображение коробки с медсестрой, держащей меньшую коробку с тем же изображением.



Так что в теории, могут быть бесконечные медсестры и бесконечные коробки.

Но на практике нет бесконечных коробок, потому что изображение имеет некоторое разрешение, и мы не можем опуститься ниже 1 пикселя.

Таким образом, существует конечное число коробок.

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

Давайте посмотрим, что произойдет, когда мы что-то неправильно программируем.

Давайте рассмотрим, опять наш рекурсивный метод вычисления степени числа.

И давайте вызовем power (x, -2) для некоторого заданного x.



Для этого мы можем заменить вызов метода кодом.



В результате мы перейдем к вызову метода power (x, -3).

В методе power (x, -3) мы перейдем к вызову метода power (x, -4).



И так далее. Без конца.



Мы получим бесконечные вычисления в теории.

На практике мы получим переполнение в какой-то момент и ошибку.

Что же мы сделали не так?

В этом случае мы не соблюдали комментарий, что y должно быть больше или равно 0.

Поэтому мы должны учитывать две важные вещи.

Во-первых, рекурсия хороша, но мы можем перейти к бесконечным вычислениям.

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

Может быть определенное количество рекурсивных вызовов, но в какой-то момент, нам нужно достичь не рекурсивного случая.

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



Существует два способа чтения и понимания рекурсивных методов.

Один из них – это тот способ, который мы видели.

Другой, математический или нотационный способ, которые мы рассмотрим.

Предположим, нам дана задача написать рекурсивный метод.

Начнем с относительно простой задачи – написать метод на Java для вычисления факториала натурального числа.

В общем случае факториал натурального числа n вычисляется умножением всех натуральных чисел, начиная с 1 до n.



Чтобы решить эту задачу, мы будем использовать следующую стратегию.

Первая часть состоит в том, что мы предполагаем, что задача решена для более простой задачи того же рода.

Предположим, что нам нужно вычислить факториал натурального числа n, но мы уже знаем, как вычислить факториал n минус 1.



Если бы у нас был факториал n минус 1, мы просто бы умножили это число на n, чтобы получить факториал n.

Вторая часть стратегии – выявить случай, когда предыдущее рассуждение не выполняется.

Факториал 0 нельзя свести к более простому случаю, как мы это делали ранее.



Так что это базовый случай.

Мы просто говорим, что факториал 0 равен 1.

Таким образом, факториал n равен 1, если n равно 0, и факториал n равен n умножить на факториал n минус 1, если n больше 0.

Теперь у нас есть основа для записи рекурсивного метода.

Из математического уравнения легко написать рекурсивный метод.



Там мы видим базовый случай, в котором нет рекурсивного вызова.

Базовый случай получается из пограничного случая.

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