Уроки PHP - урок 9 - Рекурсия

PHP рекурсия

В прошлом уроке мы разобрали использование функций в PHP. А теперь еще немного углубимся в их использование. До этого урока мы разбирали функции такого вида:

<?php
function myFunction(){ //определение функции

}

$x = myFunction(); //вызов функции
?>

Но что будет если вызвать функцию прямо в теле функции?

<?php
function myFunction(){
  $x = myFunction()
  ...
  return $x;
}

$y = myFunction();

Такой вызов функции в теле самой функции называется рекурсией. Это кажется довольно сложным в теории на практике все намного проще.

Давайте создадим функции расчета возведения числа в степень. Из курса алгебры вы наверно помните, что n степень числа обозначает это число перемноженное на себя n раз. На php это будет выглядеть так:

<?php
function myDegree($x, $n){
  if($n == 0){
	return 1;
  }
  if($n < 0){
    return myDegree( 1/$x, -$n); // -$n значит смену знака с отрицательного на положительный
  }
  return $x * myDegree($x, $n-1); // вызов функции внутри функции
}

$y = myDegree(2, -4); // самый первый вызов функции
print $y;
?>

Давайте теперь разберем подробно эту функцию. Начнем с того что после строчки return функция больше не выполняется, а возвращает значение которое указано в return.

Первая конструкция if($n == 0) - если наша степень равна 0, то будет возвращена 1. Тут все понятно и просто степень числа 0, получите 1. Дальше, if($n < 0) - если мы задаем отрицательную степень, то мы делаем степень положительной, но при этом переворачиваем число возводимое в степень в дробь, опять же по определению степени так можно делать, чем мы и воспользовались.

Ну и последнее срабатывает если степень не равна 0 и не отрицательная, тогда мы вызываем нашу функцию при каждом уменьшение степени на 1, при этом каждый раз умножаем наше число на $x.

Давайте рассмотрим каждую итерацию (повторение) нашей функции:

1. Степень -4, число 2.

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

2. Степень 4, число 0,5.

Степень положительная и не равна 0, поэтому мы проходим if и выполняется

return $x * myDegree($x, $n-1)

3. Степень 3, число 0,25.

4. Степень 2, число 0,125.

5. Степень 1, число 0,0625.

Здесь сработает первый if, то есть будет возвращена 1, эта 1 будет умножена на предыдущие результаты функций и больше рекурсий не будет.

Еще одни похожий пример факториал числа. Факториал числа n будет все перемноженные числа от 1 до n. То есть для числа 6 факториал будет равен 6*5*4*3*2*1 = 720. И как вы наверно догадались использовать мы будем рекурсию.

<?php
function myRecursion($x){
  if($x == 1){
    return $x;
  }
  return $x*myRecursion($x-1);
}

$y = myRecursion(8);
print $y;
?>

Этот пример еще проще, чем первый, поэтому я оставлю вам разобрать изменения параметров для функции myRecursion.

Комментарии

Добавить комментарий

Войти, используя Loginza Google Account Yandex Mail.ru Vkontakte Facebook

Plain text

  • HTML-теги не обрабатываются и показываются как обычный текст
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.

 для функции myDegree как

 для функции myDegree

как только $n достигнет значения 0, разве значению функции не присвоится 1 вне зависимости от предыдущих вычислений и будет конец?

почему она продолжит вычисления