Рекурсивные алгоритмы на PHP. Часть 2. Польза рекурсии

В этой статье мы продолжим изучение рекурсивных алгоритмов и выясним в чём соль рекурсии.

Ханойская башня

Давным-давно, в храме города Бенарес, Великий Брама, в наказание трёх провинившихся священников, на ступенях алтаря воздвиг три высоких алмазных стержня и на одном из них сложил башню из шестидесяти четырех дисков, сделанных из чистого золота — каждый верхний диск на размер меньше нижнего. И повелел священникам переместить диски с одного стержня на другой выполняя следующие правила:
1) В одно время можно брать только один диск.
2) Нельзя класть больший диск на меньший.

Пророчество гласит: когда последний ход головоломки будет завершен — башня разрушиться и настанет Конец Света.

Такова легенда одной из самых известных математических головоломок. Если предположить что пророчество верно и священники перемещают диски со скоростью 1 диск/сек, то впереди нас ждет ещё 41 цикл длительностью в 13.7 млрд. лет. Что ж, потратим это время с умом! И посмотрим, что может поведать нам эта головоломка о рекурсии и её смысле…

И сначала мы рассмотрим итеративное решение этой задачи. Для того чтобы получить его, нам нужно рассмотреть пару конкретных примеров для различного числа дисков n, чтобы увидеть неявные закономерности в перемещении дисков, которые возникают при соблюдении правил Брамы.

Пусть у нас есть три стержня А, B и С, причем стержень A — это стержень, на котором расположены диски в начале. Стрежень B — это промежуточный стержень. И стержень C — это стержень, на котором должны оказаться диски в самом конце. Запишем первые несколько решений этой головоломки для разных n:

n (число дисков)	Последовательность ходов
1	A->C
2	A->B A->C B->C
3	A->C A->B C->B A->C B->A B->C A->C

Здесь операция X->Y означает что нужно взять диск со стержня X и поместить на стержень Y. Очевидна следующая закономерность: количество необходимых ходов для решения равно

Это утверждение можно доказать следуя математической индукции, но мы не будем с вами этого делать, так как это не входит в нашу цель изучения рекурсии на PHP. Обнаружить ещё одну закономерность в этих данных гораздо сложнее, поэтому решим ещё эту головоломку для n = 4. Получим:

A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C

Если пронумеровать каждую пару индексом от 1 до 3-х мы можем заметить, что одни и те же пары стержней будут иметь одинаковый индекс.

1 (A->B)
2 A->C
3 B->C
1 (A->B)
2 C->A
3 C->B
1 (A->B)
2 A->C
3 B->C
1 (B->A)
2 C->A
3 B->C
1 (A->B)
2 A->C
3 B->C

Таким образом мы имеем следующую закономерность: перемещения между одинаковыми парами стержней повторяются раз в три хода. Это так же можно доказать согласно принципу математической индукции, но вернёмся к нашей задаче. Теперь когда мы обнаружили эти две закономерности мы можем записать их в виде кода:

<?php

  // Пример итеративного алгоритма решения задачи о Ханойских башнях

  function towers($n, $a, $c, $b){


    // Общее число ходов необходимых для решения
    $totalMoves = pow(2,$n) - 1;

    if($n % 2 == 0){
      $d = $b;
      $b = $c;
      $c = $d;
    }

    // Определение пары стержней для перемещения дисков
    for($i = 1; $i <= $totalMoves; $i++){
      $j = $i % 3;
      switch ($j) {
        case 1:
          echo $a,"<>",$c," ";
          break;
        case 2:
          echo $a,"<>",$b," ";
          break;
        case 0:
          echo $b,"<>",$c," ";
          break;
      }
    }
  }
?>

<?php

// Пример итеративного алгоритма решения задачи о Ханойских башнях

function towers($n, $a, $c, $b){

// Общее число ходов необходимых для решения

$totalMoves = pow(2,$n) - 1;

if($n % 2 == 0){

$d = $b;

$b = $c;

$c = $d;

}

// Определение пары стержней для перемещения дисков

for($i = 1; $i <= $totalMoves; $i++){

$j = $i % 3;

switch ($j) {

case 1:

echo $a,"<>",$c," ";

break;

case 2:

echo $a,"<>",$b," ";

break;

case 0:

echo $b,"<>",$c," ";

break;

}

Здесь есть ещё один участок, который отвечает за то, чтобы при четном количестве дисков стержни B и С поменялись местами. Эта третья закономерность, которая прячется на виду, и её легко не заметить.

К сожалению этот алгоритм может выдать нам только пары стержней, между которыми нужно совершать перемещения, но без указания направления перемещения дисков. А для того, чтобы указать направление, в этот алгоритм нужно добавить первоначальные правила Брамы. И чтобы это сделать нам придётся внедрить в наш код объектную модель самой задачи.

Каждый маг строит башню, чем больше башня — тем больше сила мага.

Цитата из фильма «Меч короля Артура»

Используя описание самой задачи, правила Брамы, а так же обнаруженные закономерности, у нас получится что-то вроде:

<?php

  // Пример итеративного алгоритма решения задачи о Ханойских башнях
  // с использованием ООП

  class Tower{
    private $S;   // Состояние башни (какие диски стоят на каком месте)
    private $top; // Номер верхнего не заполненного диском места
    public $name; // Имя башни

    function Tower($name, $n, $void){
      $this->S = array_fill(0,$n,0);
      $this->top = 0;
      $this->name = $name;

      // Создание дисков различных размеров
      if($void != true){
        for($i = 0; $i < $n; $i++){
          $this->S[$i]= $n - $i;
        }
        $this->top = $n;
      }
    }

    function getTop(){
      if($this->top == 0)
        return 0;
      return $this->S[$this->top - 1];
    }

    function isEmpty(){
      return $this->S[0] == 0;
    }

    function isFull(){
      return $this->S[sizeof($this->S) - 1] != 0;
    }

    // Взять диск
    function pop(){
      if(!$this->isEmpty()){
        $ring = $this->S[$this->top - 1];
        $this->S[$this->top - 1] = 0;
        $this->top--;
        return $ring;
      }
      return 0;
    }

    // Положить диск на башню
    function push($ring){
      if(!$this->isFull()){
        $this->S[$this->top] = $ring;
        $this->top++;
      }
    }
  }

  // Переместить диск между башнями
  function move($tower1, $tower2){
    if($tower1->isEmpty()){
      $tower1->push($tower2->pop());
      echo $tower2->name,"->",$tower1->name," ";

    } elseif($tower2->isEmpty()) {
      $tower2->push($tower1->pop());
      echo $tower1->name,"->",$tower2->name," ";

    } elseif($tower1->getTop() > $tower2->getTop()) {
      $tower1->push($tower2->pop());
      echo $tower2->name,"->",$tower1->name," ";

    } else {
      $tower2->push($tower1->pop());
      echo $tower1->name,"->",$tower2->name," ";
    }
  }

  // Главная функция
  function towers($n, $a, $c, $b){

    $towerA = new Tower($a, $n, false);
    $towerB = new Tower($b, $n, true);
    $towerC = new Tower($c, $n, true);

    $totalMoves = pow(2,$n) - 1;

    if($n % 2 == 0){
      $name = $towerB->name;
      $towerB->name = $towerC->name;
      $towerC->name = $name;
    }

    for($i = 1; $i <= $totalMoves; $i++){
      $j = $i % 3;
      switch ($j) {
        case 1:
          //echo $a,"<>",$c," ";
          move($towerA, $towerC);
          break;
        case 2:
          //echo $a,"<>",$b," ";
          move($towerA, $towerB);
          break;
        case 0:
          //echo $b,"<>",$c," ";
          move($towerB, $towerC);
          break;
      }
    }
  }
?>

100

101

102

103

104

105

106

107

108

109

110

111

112

<?php

// Пример итеративного алгоритма решения задачи о Ханойских башнях

// с использованием ООП

class Tower{

private $S; // Состояние башни (какие диски стоят на каком месте)

private $top; // Номер верхнего не заполненного диском места

public $name; // Имя башни

function Tower($name, $n, $void){

$this->S = array_fill(0,$n,0);

$this->top = 0;

$this->name = $name;

// Создание дисков различных размеров

if($void != true){

for($i = 0; $i < $n; $i++){

$this->S[$i]= $n - $i;

}

$this->top = $n;

}

function getTop(){

if($this->top == 0)

return 0;

return $this->S[$this->top - 1];

}

function isEmpty(){

return $this->S[0] == 0;

}

function isFull(){

return $this->S[sizeof($this->S) - 1] != 0;

}

// Взять диск

function pop(){

if(!$this->isEmpty()){

$ring = $this->S[$this->top - 1];

$this->S[$this->top - 1] = 0;

$this->top--;

return $ring;

}

return 0;

}

// Положить диск на башню

function push($ring){

if(!$this->isFull()){

$this->S[$this->top] = $ring;

$this->top++;

}

// Переместить диск между башнями

function move($tower1, $tower2){

if($tower1->isEmpty()){

$tower1->push($tower2->pop());

echo $tower2->name,"->",$tower1->name," ";

} elseif($tower2->isEmpty()) {

$tower2->push($tower1->pop());

echo $tower1->name,"->",$tower2->name," ";

} elseif($tower1->getTop() > $tower2->getTop()) {

$tower1->push($tower2->pop());

echo $tower2->name,"->",$tower1->name," ";

} else {

$tower2->push($tower1->pop());

echo $tower1->name,"->",$tower2->name," ";

}

// Главная функция

function towers($n, $a, $c, $b){

$towerA = new Tower($a, $n, false);

$towerB = new Tower($b, $n, true);

$towerC = new Tower($c, $n, true);

$totalMoves = pow(2,$n) - 1;

if($n % 2 == 0){

$name = $towerB->name;

$towerB->name = $towerC->name;

$towerC->name = $name;

}

for($i = 1; $i <= $totalMoves; $i++){

$j = $i % 3;

switch ($j) {

case 1:

//echo $a,"<>",$c," ";

move($towerA, $towerC);

break;

case 2:

//echo $a,"<>",$b," ";

move($towerA, $towerB);

break;

case 0:

//echo $b,"<>",$c," ";

move($towerB, $towerC);

break;

}

Теперь мы можем убедиться что наш алгоритм работает правильно для разных значений n. Мы затратили уйму времени и строк, чтобы написать этот алгоритм. А теперь сравним этот алгоритм с его рекурсивной версией.

Стандартное решение задачи о Ханойских башнях состоит в том, чтобы переместить n-1 диск с начального стержня A на стержень B, используя стержень C как промежуточный, затем переместить диск со стержня А на конечный стержень C, и после этого переместить оставшиеся диски со стрежня B на стержень C, используя стержень А как промежуточный. Эти три этапа отражены в следующем коде.

<?php

  // Пример рекурсивного решения задачи о Ханойских башнях

  function towers($n, $a, $c, $b){
    if($n==1){
      echo $a,"->",$c," ";
    } else {
      towers($n-1,$a,$b,$c);
      echo $a,"->",$c," ";
      towers($n-1,$b,$c,$a);
    }
  }
?>

<?php

// Пример рекурсивного решения задачи о Ханойских башнях

function towers($n, $a, $c, $b){

if($n==1){

echo $a,"->",$c," ";

} else {

towers($n-1,$a,$b,$c);

echo $a,"->",$c," ";

towers($n-1,$b,$c,$a);

}

Что ж, он выглядит гораздо проще: почти в десять раз компактнее его итеративной версии. Это одно из преимуществ рекурсии, которое имеет множество последствий. В некоторых случаях выгоднее писать рекурсивный код, так как его будет легче поддерживать, он будет выглядеть лаконично, его будет легче понять, а так же легче заниматься его отладкой и он займёт меньше времени на разработку, то есть это даёт возможность сэкономить личное время.

Теперь сравним время выполнения этих двух алгоритмов. Я запустил эти два алгоритма на четырехядерном AMD Phenom и у меня получилась такая таблица.

n (число дисков)	Время выполнения алгоритма, с
n (число дисков)	Рекурсии	Итерации
5	0,0001	0,0003
10	0,0044	0,0095
15	0,1599	0,2281
20	5,2030	7,6011

Мы видим, что при больших значениях n рекурсивный код выигрывает по времени примерно в 1.5 раза. Это второе преимущество, которое может быть существенным при разработке высконагруженных систем, когда дорога каждая секунда процессорного времени. В некоторых случаях рекурсивный код может работать быстрее его итеративных аналогов, и это даёт возможность сэкономить вычислительные ресурсы.

Очевидно так же что для нашей задачи рекурсивное решение более экономично в плане затрат компьютерной памяти, так как не требует хранения объектной модели. Это может быть третьим преимуществом рекурсии.

Итак, подведём итоги. Мы изучили различные аспекты реализации рекурсивных алгоритмов на PHP. Теперь мы знаем:

1) Что такое рекурсия и какие виды рекурсии бывают. (Читать с начала первой части) (Английский юмор)

2) Применяя рекурсию нужно быть осторожным, т.к. есть вероятность переполнения стека рекурсивных вызовов при больших значениях глубины рекурсии или в случае бесконечной рекурсии.

3) В некоторых случаях рекурсивные алгоритмы могут работать медленнее их итеративных аналогов. (Вычисления последовательности чисел Фибоначчи и т.п.),

4) Для достижения большей эффективности в комбинации с рекурсией можно:

использовать подход восходящего динамического программирования (задача разбивается на подзадачи, и каждая подзадача решается только один раз)
использовать ООП (например, чтобы избежать затрат на избыточное копирование аргументов в стеке)

5) В общем и целом рекурсия позволяет абстрагироваться от конкретных деталей задачи при её решении. И как следствие, это может помочь нам:

сэкономить личное время и ресурсы
сэкономить вычислительные ресурсы такие как память и процессорное время.

В заключении я хочу отметить, что тема рекурсии далеко не исчерпана и мы встретимся с ней снова в наших статьях, когда речь зайдёт о фракталах.

Комментарии 2

Ігор

28.08.2019 в 06:51

отличное и короткое определение рекурсии было дано в толковом словаре Даля:
РЕКУРСИЯ — см. рекурсия

Ответить
Сергей

21.10.2019 в 21:29

Это конечно всё замечательно, но как думать, чтобы понять смысл рекурсии и отразить её в коде — вот это вопрос.

Ответить

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

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Рекурсивные алгоритмы на PHP. Часть 2. Польза рекурсии

Ханойская башня

Похожие записи:

Комментарии 2

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