Функции и процедуры. Рекурсия

Начнем обсуждение этой темы с задачи о Ханойских башнях. Головоломка “Ханойские башни” состоит из трёх стержней, на один из которых нанизано несколько колец. Все кольца имеют разный диаметр и расположены снизу вверх по убыванию диаметра.

За один ход разрешается снять верхнее кольцо с любого стержня и переместить его на другой стержень. При этом запрещается класть кольцо на кольцо меньшего диаметра.

 

Вот один из возможных алгоритмов. Пронумеруем кольца сверху вниз числами от 1 до n. Пусть нам нужно переложить n колец с первого стержня на третий. Будем рассуждать по индукции.

Если n=1, то решение задачи очевидно.

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

1.       Перекладываем верхние n-1 колец с первого стержня на второй.

2.       Перекладываем последнее (самое большое) кольцо с первого стержня на третий.

3.       Перекладываем n-1 колец со второго стержня на третий.

Попробуем написать процедуру, печатающую последовательность перекладываний согласно описанному алгоритму.

 

procedure Hanoi (n, i, j, k : integer);      {переложить n колец

с i-го стержня на j-й, использую k-й стержень в качестве вспомогательного}

begin

  if n=1 then writeln (i,’->’,j)

  else begin

    Hanoi(n-1,i,k,j);      {Перекладываем n-1 колец

 с i-го стержня на k-й}

    writeln (i,’->’,j);      {Перекладываем оставшееся кольцо

 с i-го стержня на j-й}

    Hanoi(n-1,k,j,i);      {Перекладываем n-1 колец

 с k-го стержня на j-й}

  end;

end;

 

Обратите внимание: наша процедура вызывает сама себя (но с другими параметрами). Так, Hanoi(2, 1,2,3) вызывает Hanoi(1, 1,3,2) и Hanoi(1, 3,2,1).

 

Определение. Процедуры, вызывающие себя в процессе работы называются рекурсивными.

 

Для того, чтобы программа не зацикливалась, рекурсивная процедура должна содержать терминальное условие – условие, при котором новых вызовов функции не происходит. В нашем случае таким условием служит условие n = 1. Уже при n = 3 последовательность вызовов функций будет довольно сложной, но мы пока не будем углубляться в механизмы работы рекурсии, а перейдем к следующей задаче.