Как работает рекурсия?

Question

[adil16]

Как работает рекурсия возведения в степень в данном случае?

function myRecursion($x, $n) {
  if ($n == 0) {
    return 1;
  }
  if ($n < 0) {
    return myRecursion(1/$x, $n);
  }else
  return $x * myRecursion($x, $n-1);
}

var_dump(myRecursion(5, 5));

Мне непонятно как работает для отрицательных чисел, ведь число в отрицательной степени равно 1/число с той же положительной степенью. myRecursion(1/$x, $n)- откуда данная функция знает, что $n это степень числа $x? Как это работает для положительной степени тоже непонятно.

Answer 1

[Fallenyasha]

А оно точно работает?
Потому что вроде как при отрицательной степени должно быть return myRecursion(1/$x, -$n);
Для положительной степени работает так:
myRecursion (5, 5) =
5 * myRecursion (5, 4) =
5 * 5 * myRecursion (5, 3) =
5 * 5 * 5 * myRecursion (5, 2) =
5 * 5 * 5 * 5 * myRecursion (5, 1) =
5 * 5 * 5 * 5 * 5 * myRecursion (5, 0) =
5 * 5 * 5 * 5 * 5 * 1

Comments

[adil16]

а почему функция 5 умножает только на 5, а не умножает еще на $n? извините за тупые вопросы.

[Fallenyasha]

Не совсем понял вопрос, вы про какую строчку кода?

[adil16]

Fallenyasha, return $x * myRecursion($x, $n-1);
вот здесь, что значит , почему 5 умножается на 5, откуда эта 5-ка постоянно берется, это $x которая в скобках?

[Fallenyasha]

Здесь 5 умножается на значение этой же функции от x, n-1, реализуется простая математическая последовательность f(x, n) = x * f(x, n - 1)

Основной вызов функции возвращает 5 умноженное на (5, 4), которое возвращает 5 умноженное на (5, 3), которое ...., которое возвращает 5 умноженное на (5, 0), которое возвращает 1.

Почитайте объяснения, что такое рекурсия: хабр, метанит, вики и вики

[adil16]

Fallenyasha, ознакомился, последний вопрос в случае положительной степени $n служит как бы счетчиком, я посчитал что возвращает myRecursion($x, $n-1), в конечном итоге условие возвращает $n = 1 и рекурсия идет в обратную сторону . а как считать, когда степень отрицательная?

[Fallenyasha]

При отрицательной степени мы разворачиваем уравнение из x^(-n) в (1/x)^n и дальше как обычно.