Рекурсивное решение

void hanoi( short a, // № начальной площадки

short b, // № конечной площадки

short n){ // Число дисков

if (n == 1){ // Конец рекурсии

printf(" %2d %2d\n", a, b);

return;

}

hanoi(a, 6-a-b, n-1);

printf(" %2d %2d\n", a, b);

hanoi(6-a-b, b, n-1);

} // End hanoi

При каждом рекурсивном вызове процедуры hanoi транслятор помещает значения аргументов a, b, n в так называемый стек вызова, т.е. программисту не надо вручную записывать операции помещения в стек и извлечения из стека.

В нерекурсивном решении возможны 2 варианта реализации стека: в виде массива и в виде списка.

Нерекурсивное решение. Стек в виде массива

# define DEEP 20 // Максимальная глубина стека

void hanoi( short a, // Исходная площадка

short b, // Площадка - цель

short n){ // Число дисков

short stack[DEEP][3],

i, // Индикатор уровня стека

fl; // 0 – стек пуст. Конец вычислений

fl = 1;

i = -1;

while (fl){

if (n > 1){ // Заполнение стека

i++;

stack[ i ][0] = a;

stack[ i ][1] = b;

stack[ i ][2] = n;

/* Подготовить первое обращение */

b = 6-a-b;

n--;

} else {

if (i >= 0){// Стек не пуст

/* Печать вершины уровня 1 */

printf(" %2d %2d\n", a, b);

/* Извлечь данные из стека */

a = stack[ i ][0];

b = stack[ i ][1];

n = stack[ i ][2];

/* Печать "корня" */

printf(" %2d %2d\n", a, b);

/* Подготовить второе обращение */

a = 6-a-b;

n--;

/* Убрать вершину из стека */

i--;

} else { // Стек пуст

fl = 0;

}

}

} // End while

/* Печать последней вершины */

printf(" %2d %2d\n", a, b);

} // End hanoi