22.3. Рекурсия без локальных переменных

Пример 22-13. Ханойские Башни

#! /bin/bash
#
# Ханойские Башни
# Bash script
# Copyright (C) 2000 Amit Singh. All Rights Reserved.
# http://hanoi.kernelthread.com
#
# Тестировался под bash 2.05b.0(13)-release
#
#  Используется в "Advanced Bash Scripting Guide"
#+ с разрешения автора.
#  С небольшими изменениями, внесенными автором документа.

#=================================================================#
#  Ханойские Башни -- это древняя математическая головоломка.
#  Дается три вертикальных стержня.
#  На первый нанизан набор колец.
#  Эти кольца представляют собой плоские диски с дыркой по-середине,
#+ так что они могут свободно скользить по стержню.
#  Кольца имеют различный диаметр, и изначально расположены на первом стержне
#+ в порядке убывания их диаметров.
#  Наименьшее кольцо расположено сверху, наиболшее -- внизу.
#
#  Суть задачи заключается в том, чтобы перенести кольца с первого
#+ стержня на последний так, чтобы порядок следования колец не изменился.
#  Кольца можно перемещать со стержня на стержень только по одному за раз.
#  Можно помещать кольца обратно на тот же самый стержень.
#  При перемещении нельзя класть больший диск на меньший.
#
#  Для небольшого количества колец требутся некоторое количество перемещений.
#+ Каждое дополнительное кольцо
#+ увеличивает необходимое количество перемещений примерно в два раза,
#+ при этом "стратегия" перемещения усложняется все больше и больше.
#
#  За дополнительной информацией обращайтесь на http://hanoi.kernelthread.com.
#
#
#         ...                   ...                    ...
#         | |                   | |                    | |
#        _|_|_                  | |                    | |
#       |_____|                 | |                    | |
#      |_______|                | |                    | |
#     |_________|               | |                    | |
#    |___________|              | |                    | |
#   |             |             | |                    | |
# .--------------------------------------------------------------.
# |**************************************************************|
#          #1                   #2                      #3
#
#=================================================================#


E_NOPARAM=66  # Сценарий запущен без параметров.
E_BADPARAM=67 # Неверное число колец.
Moves=        # Глобальная переменная, хранит число перемещений.
              # Добавлено в оригинальный сценарий.

dohanoi() {   # Рекурсивная функция.
    case $1 in
    0)
        ;;
    *)
        dohanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
              let "Moves += 1"  # Добавлено в оригинальный сценарий.
        dohanoi "$(($1-1))" $4 $3 $2
        ;;
    esac
}

case $# in
1)
    case $(($1>0)) in     # Как минимум должен быть хотя бы один диск.
    1)
        dohanoi $1 1 3 2
        echo "Всего перемещений = $Moves"
        exit 0;
        ;;
    *)
        echo "$0: Неверное число колец";
        exit $E_BADPARAM;
        ;;
    esac
    ;;
*)
    echo "Порядок использования: $0 N"
    echo "       Где \"N\" -- это число колец."
    exit $E_NOPARAM;
    ;;
esac

# Упражнения:
# ---------
# 1) Будут ли исполнены дополнительные команды, если разместить их ниже этой строки?
#    Почему нет? (Это так просто!)
# 2) Объясните -- как работает функция "dohanoi".
#    (А вот это уже сложнее)