Visualizza wikitesto di LOGO/Ricorsività

{{LOGO}}

Una [[LOGO/Procedure|procedura]] si dice '''ricorsiva''' se all'interno delle istruzioni che esegue c'è una chiamata a sé stessa.

[[Immagine:LOGO recursive star.png|thumb|Il risultato della procedura a fianco (la tartaruga è stata nascosta).]]

Ad esempio:
<pre>
 to stellaricorsiva :lato
   forward :lato
   right 160
   forward :lato
   right 120
   stellaricorsiva :lato
 end
</pre>

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:

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

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.

{{Avanzamento|100%}}

[[Categoria:LOGO|Ricorsività]]