Возведение числа в степень через рекурсию

Для начала вспомним, какие частные случаи необходимо учесть при возведении в степень (очевидный вариант возведения положительного числа в положительную степень опустим):

• Возведение в отрицательную степень:

  • х^(-p) = 1 / x^p

• Возведение числа в степень 0 или 1:

  • x^0 = 1

  • x^1 = x

• Возведение в степень чисел 0 или 1:

  • 0^p = 0

  • 1^p = 1

• Исключение (невозможно получить ответ):

  • 0^p при p <= 0

Итак, начнем вычисление х^p. Сначала убедимся, что входные параметры не попадают под исключение (строка 2). Затем проверим частные случаи (строка 5):

public static double power(double x, int p) {
  if (x == 0 && p <= 0) {
    throw new ArithmeticException("Невозможно возвести 0 в степень меньше 1");
  }
  if (x == 1 || x == 0) return x;

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

Следующим шагом напишем логику работы возведения в степень. Первая строка - возведение в положительную, вторая - в отрицательную.

if (p > 1) return x * power(x, --p);
if (p < 1) return 1 / x * power(x, ++p);

Сейчас наша рекурсия будет отрабатывать, как задумано, пока степень p не станет равна 1. Это и есть наш последний частный случай! Поскольку при возведении в первую степень не требуется использовать рекурсию, мы можем сделать p = 1 нашим базовым случаем.

if (p > 1) return x * power(x, --p);
if (p < 1) return 1 / x * power(x, ++p);
return x;

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

Весь код целиком:

public static double power(double x, int p) {
        if (x == 0 && p <= 0) {
          throw new ArithmeticException("Невозможно возвести 0 в степень меньше 1");
        }
        if (x == 1 || x == 0) return x;
        if (p > 1) return x * power(x, --p);
        if (p < 1) return 1 / x * power(x, ++p);
        return x;
    }

На первый взгляд, может показаться трудным для понимания сценарий возведения в отрицательную степень. А именно, почему используется p < 1? Давайте разберемся.
Допустим, мы имеем x = 2 и p = -1. В таком случае, после первой итерации мы получим:

if (p < 1) return 1 / 2 * power(2, 0);

Поскольку условие p < 1 будет верным и на второй итерации, выражение примет вид:

if (p < 1) return 1 / 2 * 1 / 2 * power(2, 1);

По логике вещей, мы уже проскочили наш ответ, ведь 2^-1 = 1/2. Однако, поскольку на следующей итерации p = 1, результатом работы метода окажется x. Таким образом, в итоге наше выражение примет вид:

if (p < 1) return 1 / 2 * 1 / 2 * 2;

И в итоге мы получим верный ответ.