23.3. Récursion sans variables locales

#! /bin/bash
#
# La tour d'Hanoi
# Script bash
# Copyright (C) 2000 Amit Singh. All Rights Reserved.
# http://hanoi.kernelthread.com
#
# Dernier test avec bash version 2.05b.0(13)-release
#
#  Utilisé dans le "Guide d'écriture avancé des scripts Bash"
#+ Avec l'autorisation de l'auteur du script.
#  Légèrement modifié et commenté par l'auteur d'ABS.

#=================================================================#
#  La tour d'Hanoi est un puzzle mathématique attribué à Édouard Lucas,
#+ un mathématicien français du 19è siècle.
#  Il y a un ensemble de trois positions verticales dans une base.
#  Le premier poste dispose d'un ensemble d'anneaux empilés.
#  Les anneaux sont des disques plats avec un trou en leur centre,
#+ de manière à être placés sur les batons.
#  Les anneaux ont des diamètres différents et ils s'assemblent en ordre 
#+ descendant suivant leur taille.
#  La plus petite est au-dessus et la plus large à la base.
#
#  Le problème consiste à transférer la pile d'anneaux d'un baton à un autre.
#  Vous pouvez bouger seulement un anneau à la fois.
#  Il vous est permis de replacer les anneaux à leur baton d'origine.
#  Vous pouvez placer un petit anneau sur un plus gros mais pas le contraire.
#  Encore une fois, il est interdit de placer un gros anneau sur un plus petit.
#
#  Pour un petit nombre d'anneaux, seuls quelques mouvements sont nécessaires.
#+ Pour chaque anneau supplémentaire, le nombre de déplacements requis double
#+ approximativement et la "stratégie" devient de plus en plus complexe.
#
#  Pour plus d'informations, voir http://hanoi.kernelthread.com.
#
#
#         ...                   ...                    ...
#         | |                   | |                    | |
#        _|_|_                  | |                    | |
#       |_____|                 | |                    | |
#      |_______|                | |                    | |
#     |_________|               | |                    | |
#    |___________|              | |                    | |
#   |             |             | |                    | |
# .--------------------------------------------------------------.
# |**************************************************************|
#          #1                   #2                      #3
#
#=================================================================#


E_SANSPARAM=66    # Aucun paramètre passé au script.
E_MAUVAISPARAM=67 # Nombre illégal de disques.
Deplacements=     # Variable globale contenant le nombre de déplacements.
                  # Modifications du script original.

fait_hanoi() {   # Fonction récursive.
    case $1 in
    0)
        ;;
    *)
        fait_hanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
        let "Deplacements += 1"  # Modification du script original.
        fait_hanoi "$(($1-1))" $4 $3 $2
        ;;
    esac
}

case $# in
1)
    case $(($1>0)) in     # Il doit y avoir au moins un disque.
    1)
        fait_hanoi $1 1 3 2
        echo "Nombre total de déplacements = $Deplacements"
        exit 0;
        ;;
    *)
        echo "$0: valeur illégale pour le nombre de disques";
        exit $E_MAUVAISPARAM;
        ;;
    esac
    ;;
*)
    echo "usage: $0 N"
    echo "       où \"N\" est le nombre de disques."
    exit $E_SANSPARAM;
    ;;
esac

# Exercices:
# ---------
# 1) Est-ce que les commandes au delà de ce point seront exécutées ?
#    Pourquoi ? (Facile)
# 2) Expliquer le fonctionnement de la fonction "fait_hanoi".
#    (Difficile)