Se il linguaggio di programmazione prevede la ricorsione… una SUB A può chiamare la SUB A, se stessa, per svolgere lo stesso compito ma con un’stanza diversa
La SUB A chiama la SUB A, … ma a ogni passo il problema diventa più semplice (i valori dei parametri si riducono) finché l’istanza diventa un caso particolare che non necessita di un’ulteriore chiamata ricorsiva e si ritorna all’indietro fino alla chiusura di tutte le chiamate.
Perché la ricorsione funzioni ci sono 2 regole da rispettare
- è previsto un caso particolare (una dimensione minima del problema) che non richiede ulteriori chiamate
- la dimensione del problema diminuisce a ogni chiamata.
La ricorsione può essere complicata
- In passato le risorse hardware (RAM) ridotte ponevano un limite al numero massimo di chiamate.
- Multipla: nel codice del sottoprogramma la chiamata ricorsiva si presenta più volte (2, …)
- Indiretta: il sottoprogramma A chiama un altro sottoprogramma B che a sua volta … che a sua volta chiama A
La ricorsione può essere facile
- la ricorsione può sostituire l’iterazione (LISP, …) e viceversa
- alcuni problemi ammettano formulazioni ricorsive immediate quindi…
- alcuni problemi ammettono formulazioni ricorsive immediate mentre la riformulazione iterativa risulta piuttosto difficile
C, C++, Java, …
void XYZ(parametri_formali)
{
...
XYZ(parametri_attuali);
...
}
double XYZ(parametri_formali)
{
...
x=XYZ(parametri_attuali);
...
return espr;
}
Pascal
Procedure XYZ(parametri_formali);
...
Begin
...
XYZ(parametri_attuali);
...
End;
Function XYZ(parametri_formali): Double;
...
Begin
...
x=XYZ(parametri_attuali);
...
XYZ:=espr;
End;
Python
def XYZ(parametri_formali):
...
XYZ(parametri_attuali)
...
def XYZ(parametri_formali):
...
x=XYZ(parametri_attuali)
...
return espr
Visual Basic
Sub XYZ(parametri_formali)
...
Call XYZ(parametri_attuali)
...
End Sub
Function XYZ(parametri_formali) As Double
...
x=XYZ(parametri_attuali)
...
XYZ=espr
End Function