24.3. Récursion sans variables locales

#!/bin/bash
# fibo.sh : Fibonacci sequence (recursive)
# Author: M. Cooper
# License: GPL3

# ---------------------------------
# Fibo(0) = 0
# Fibo(1) = 1
# else
#   Fibo(j) = Fibo(j-1) + Fibo(j-2)
# ---------------------------------

MAXTERM=15       # Number of terms (+1) to generate.
MINIDX=2         # If idx is less than 2, then Fibo(idx) = idx.

Fibonacci ()
{
  idx=$1   # Doesn't need to be local. Why not?
  if [ "$idx" -lt "$MINIDX" ]
  then
    echo "$idx"  # First two terms are 0 1 ... see above.
  else
    (( --idx ))  # j-1
    term1=$( Fibonacci $idx )   #  Fibo(j-1)

    (( --idx ))  # j-2
    term2=$( Fibonacci $idx )   #  Fibo(j-2)

    echo $(( term1 + term2 ))
  fi
  #  An ugly, ugly kludge.
  #  The more elegant implementation of recursive fibo in C
  #+ is a straightforward translation of the algorithm in lines 7 - 10.
}

for i in $(seq 0 $MAXTERM)
do  # Calculate $MAXTERM+1 terms.
  FIBO=$(Fibonacci $i)
  echo -n "$FIBO "
done
# 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
# Takes a while, doesn't it? Recursion in a script is slow.

echo

exit 0

#! /bin/bash
#
# La tour d'Hanoi
# Script bash
# Copyright (C) 2000 Amit Singh. All Rights Reserved.
# http://hanoi.kernelthread.com
#
# Testé avec bash version 2.05b.0(13)-release
# Fonctionne aussi avec Bash version 3.x.
#
#  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
#+ ou pp. 186-92 de _The Armchair Universe_ par A.K. Dewdney.
#
#
#         ...                   ...                    ...
#         | |                   | |                    | |
#        _|_|_                  | |                    | |
#       |_____|                 | |                    | |
#      |_______|                | |                    | |
#     |_________|               | |                    | |
#    |___________|              | |                    | |
#   |             |             | |                    | |
# .--------------------------------------------------------------.
# |**************************************************************|
#          #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.
                  # Modification du script original.

fait_hanoi() {   # Fonction récursive.
    case $1 in
    0)
        ;;
    *)
        fait_hanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
        ((Deplacements++))  # 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) # Instruction case imbriquée.
          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 -- voir la référence sur Dewdney ci-dessus.)