LOGO/Ricorsività: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Sostituzione automatica (-\[\[[Ll]inguaggio[ _]LOGO +[[LOGO) |
Nessun oggetto della modifica |
||
Riga 1:
{{LOGO}}
Una [[LOGO/Procedure|procedura]] si dice '''ricorsiva'''
[[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
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|
[[Categoria:LOGO|Ricorsività]]
| |||