LOGO/Ricorsività

Una procedura si dice ricorsiva se all'interno delle istruzioni che esegue c'è una chiamata a sé stessa.

Il risultato della procedura a fianco (la tartaruga è stata nascosta).

Ad esempio:

 to stellaricorsiva :lato
   forward :lato
   right 160
   forward :lato
   right 120
   stellaricorsiva :lato
 end

Il risultato di questa semplice procedura ricorsiva sarà una stella disegnata sullo schermo e una tartaruga che sfreccia sulle linee continuando a disegnare finché voi non la fermate in qualche modo (ad esempio con un CTRL-C).

Come tutte le procedure anche quelle ricorsive possono o meno avere parametri.

In Logo, come negli altri linguaggi funzionali, la ricorsione è il principale modo per eseguire i cicli. Un ciclo while:

while <condizione> do
  <istruzioni>

viene realizzato in Logo dalla procedura ricorsiva:

to while
  if not <condizione> [stop]
  <istruzioni>
  while

Ad esempio se voglio stampare i termini della successione di Fibonacci minori di 10000 con l'algoritmo:

a <-- 0
b <-- 1
finquando a<=10000 esegui
  stampa a
  a <-- b
  a <-- a+b

Si traduce in Logo:

to fibonacci :a :b
  if a>10000 [stop]
  print a
  fibonacci :b :a+:b
end

L'istruzione condizionale che permette di terminare la procedura ricorsiva:

if a>10000 [stop]

si chiama condizione di terminazione.

Le procedure dove la chiamata ricorsiva è l'ultima istruzione che viene eseguita, si dicono terminali in caso contrario si dicono non terminali.

È interessante cercare di immaginare l'effetto della seguente procedura non terminale, e poi provarla:

to fibonacci :a :b
  if a>10000 [stop]
  fibonacci :b :a+:b
  print a
end

Tipici esempi di procedure ricorsive terminali e non terminali sono:

to spirale :lato :angolo :incremento
  if lato>100 [stop]
  forward :lato
  right :angolo
  spirale :lato+:incremento :angolo :incremento
end

to albero :ramo :angolo :fattore
  if :ramo<2 [stop]
  forward :ramo
  left :angolo
  albero :ramo*:fattore :angolo :fattore
  right :angolo*2
  albero :ramo*:fattore :angolo :fattore
  left :angolo
  back :ramo
end

chiamate rispettivamente con argomenti simili a questi:

spirale 1 92 1 albero 90 60 0.7

Le funzioni ricorsive si prestano a tradurre in algoritmo le definizioni matematiche ricorsive. ad esempio una potenza di base b ed esponente e può essere definita:

$b^{e}=\left\{{\begin{matrix}1&{\mbox{se }}e=0\\b\cdot b^{e-1}&{\text{se }}e>0\end{matrix}}\right.$

In Logo diventa:

to potenza :base :esp
  if equalp :esp 0 [output 1]
  output :base * potenza :base :esp-1
end

Da osservare che nonostante la chiamata ricorsiva sia l'ultima cosa scritta nella funzione, questa non è una funzione ricorsiva terminale, perché il prodotto:

  :base * potenza :base :esp-1

viene eseguito solo dopo che termina la chiamata ricorsiva.

Le funzioni ricorsive sono molto espressive. È possibile scrivere in Logo una funzione di poche righe che dà come risultato una frase costruita casualmente su una qualunque grammatica generativa.

Noi siamo abituati a pensare e ad agire ricorsivamente, ma non siamo abituati a descrivere procedimenti ricorsivi. Ad esempio:

• per salire una scala salgo il primo gradino poi salgo la scala rimanente.
• per cercare una parola nel vocabolario prendo una parola a caso, poi se è minore della parola cercata cerco la parola nel blocco di destra se è maggiore la cerco nel blocco di sinistra se è uguale, l'ho trovata.
• un sentiero di montagna è una curva seguita da un sentiero di montagna.