И далее нам понадобятся другие методы для всех различных значений 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.