23.3. Ricorsività senza variabili locali

#! /bin/bash
#
# La Torre di Hanoi
# Script Bash
# Copyright (C) 2000 Amit Singh. Tutti i diritti riservati.
# http://hanoi.kernelthread.com
#
# Ultima verifica eseguita con la versione bash 2.05b.0(13)-release
#
#  Usato in "Advanced Bash Scripting Guide"
#+ con il permesso dell'autore dello script.
#  Commentato e leggermente modificato dall'autore di ABS.

#========================================================================#
#  La Torre di Hanoi è un rompicapo matematico attribuito a
#+ Edouard Lucas, matematico francese del XIX secolo.
#
#  Ci sono tre pioli verticali inseriti in una base.
#  Nel primo piolo è impilata una serie di anelli rotondi.
#  Gli anelli sono dei dischi piatti con un foro al centro,
#+ in modo che possano essere infilati nei pioli.
#  I dischi hanno diametri diversi e sono impilati in ordine
#+ decrescente in base alla loro dimensione.
#  Quello più piccolo si trova nella posizione più alta,
#+ quello più grande alla base.
#
#  Lo scopo è quello di trasferire la pila di dischi
#+ in uno degli altri pioli.
#  Si può spostare solo un disco alla volta.
#  È consentito rimettere i dischi nel piolo iniziale.
#  È permesso mettere un disco su un altro di dimensione maggiore,
#+ ma *non* viceversa.
#  Ancora, è proibito collocare un disco su uno di minor diametro.
#
#  Con un numero ridotto di dischi, sono necessari solo pochi spostamenti.
#+ Per ogni disco aggiuntivo,
#+ il numero degli spostamenti richiesti approssimativamente raddoppia
#+ e la "strategia" diventa sempre più complessa.
#
#  Per ulteriori informazioni, vedi http://hanoi.kernelthread.com.
#
#
#         ...                   ...                    ...
#         | |                   | |                    | |
#        _|_|_                  | |                    | |
#       |_____|                 | |                    | |
#      |_______|                | |                    | |
#     |_________|               | |                    | |
#    |___________|              | |                    | |
#   |             |             | |                    | |
# .--------------------------------------------------------------.
# |**************************************************************|
#          #1                   #2                      #3
#
#========================================================================#


E_NOPARAM=66    # Nessun parametro passato allo script.
E_ERR_PARAM=67  # Il numero di dischi passato allo script non è valido.
Mosse=          # Variabile globale contenente il numero degli spostamenti.
                # Modifiche allo script originale.

eseguehanoi() { # Funzione ricorsiva.
    case $1 in
    0)
        ;;
    *)
        eseguehanoi "$(($1-1))" $2 $4 $3
        echo sposto $2 "-->" $3
	let "Mosse += 1"  # Modifica allo script originale.
        eseguehanoi "$(($1-1))" $4 $3 $2
        ;;
    esac
}

case $# in
1)
    case $(($1>0)) in     # Deve esserci almeno un disco.
    1)
        eseguehanoi $1 1 3 2
        echo "Totale spostamenti = $Mosse"
        exit 0;
        ;;
    *)
        echo "$0: numero di dischi non consentito";
        exit $E_ERR_PARAM;
        ;;
    esac
    ;;
*)
    echo "utilizzo: $0 N"
    echo "       Dove \"N\" è il numero dei dischi."
    exit $E_NOPARAM;
    ;;
esac

# Esercizi:
# ---------
# 1) Eventuali comandi posti in questo punto verrebbero eseguiti?
#    Perché no? (Facile)
# 2) Spiegate come agisce la funzione "eseguehanoi".
#    (Difficile)