к оглавлению

Что такое рекурсия

Рекурсией называется такая конструкция, при которой функция вызывает саму себя. Различают прямую и косвенную рекурсии. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной.

Рассмотрим классические примеры использования рекурсии - реализацию операции возведения в степень и вычисление факториала числа. Заметим, что эти примеры являются классическими только из-за их удобства для объяснения понятия рекурсии, однако они не дают выигрыша в программной реализации по сравнению с итерационным способом решения этих задач.

<?php
  function degree($x,$y)
  {
    if($y)
    {
      return $x*degree($x,$y-1);
    }
    return 1;
  }
  echo(degree(2,4)); // выводит 16
?>

Этот пример основан на том, что xy эквивалентно x*x(y-1). В этом коде задача вычисления 24 разбивается на вычисление 2*2³. Затем 2*2³ разбивается на 2*2² и так до тех пор, пока показатель не станет равным нулю.

Итерационный вариант этого примера выглядит так:

<?php
  function degree($x,$y)
  {
    for($result = 1; $y > 0; --$y)
    {
      $result *= $x;
    }
    return $result;
  }
  echo(degree(2,4)); // выводит 16
?>

Кроме того, что этот код намного легче понять, он еще и более эффективен, поскольку проход цикла обходится "дешевле" вызова функции.

<?php
  function fact($x)
  {
    if ($x < 0) return 0;
    if ($x == 0) return 1;
    return $x * fact($x - 1);
  }
  echo (fact(3)); // выводит 6
?>

Для отрицательного аргумента функция возвращает нулевое значение, так как факториал отрицательного числа не существует по определению. Для нулевого параметра функция возвращает значение 1, поскольку 0! = 1. В иных случаях вызывается та же функция с уменьшенным на 1 значением параметра, после чего результат умножается на текущее значение параметра. Т. е. происходит вычисление произведения:

k * (k - 1) * (k - 2) * ... * 3 * 2 * 1 * 1

Последовательность рекурсивных вызовов прерывается только при вызове fact(0), который и приводит к последнему значению 1 в произведении, так как последнее выражение, из которого вызывается функция, имеет вид 1 * fact(1 - 1).

Итерационно факториал можно вычислить так:

<?php
  function fact($x)
  {
    for ($result = 1; $x > 1; --$x)
    {
      $result *= $x;
    }
    return $result;
  }
  echo (fact(6)); // выводит 720
?>
к оглавлению

Знаете ли Вы, что релятивизм (СТО и ОТО) не является истинной наукой? - Истинная наука обязательно опирается на причинность и законы природы, данные нам в физических явлениях (фактах). В отличие от этого СТО и ОТО построены на аксиоматических постулатах, то есть принципиально недоказуемых догматах, в которые обязаны верить последователи этих учений. То есть релятивизм есть форма религии, культа, раздуваемого политической машиной мифического авторитета Эйнштейна и верных его последователей, возводимых в ранг святых от релятивистской физики. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 14.10.2019 - 19:26: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Вячеслава Осиевского - Карим_Хайдаров.
14.10.2019 - 03:09: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Марины Мелиховой - Карим_Хайдаров.
13.10.2019 - 18:09: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Светланы Вислобоковой - Карим_Хайдаров.
13.10.2019 - 08:05: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Декларация Академической Свободы - Карим_Хайдаров.
13.10.2019 - 08:03: ЭКОЛОГИЯ - Ecology -> Биохимия мозга от проф. С.В. Савельева и не только - Карим_Хайдаров.
12.10.2019 - 07:03: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Константина Сёмина - Карим_Хайдаров.
11.10.2019 - 08:59: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
11.10.2019 - 06:24: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
11.10.2019 - 03:57: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
11.10.2019 - 03:33: ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров.
11.10.2019 - 03:22: ЭКОЛОГИЯ - Ecology -> Глобальное потепление - миф или... миф? - Карим_Хайдаров.
09.10.2019 - 19:01: ТЕОРЕТИЗИРОВАНИЕ И МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ - Theorizing and Mathematical Design -> ФУТУРОЛОГИЯ - прогнозы на будущее - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution