Теперь нам нужно собрать все вместе.
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.
Чтобы решить эту задачу, мы будем использовать следующую стратегию.
Первая часть состоит в том, что мы предполагаем, что задача решена