Ricorsione

La ricorsione è il meccanismo di programmazione in cui una funzione fa al suo interno una chiamata a se stessa. I linguaggi moderni, quali il C, permettono infatti a una funzione di richiamare se stessa al loro interno (al contrario di linguaggi quali il Fortran, in cui questo non è possibile).

Il metodo di rappresentazione di variabili in memoria che permette di effettuare chiamate ricorsive è quello dello stack dei record di attivazione, in cui ogni attivazione di una procedura crea una nuova area di memoria in cui sono contenute le variabili locali di questa attivazione.

L'uso della ricorsione può rendere più semplice la programmazione. Nel caso delle lista, il vantaggio consiste nel fatto che funzioni ricorsive possono venire scritte tenendo conto della definizione ricorsiva di lista, per cui si ottengono facilmente dei programmi corretti senza dover simulare lo stato della memoria. Ci sono anche situazioni (per esempio, i programmi sugli alberi) in cui la ricorsione è il solo modo naturale di realizzare delle funzioni.

  1. stack, heap e record di attivazione
  2. il punto di ritorno
  3. la serie di Fibonacci, implementata con una funzione ricorsiva
  4. la ricorsione su liste, stampa di una lista
  5. stampa di una lista al contrario
  6. lettura di una lista da file, in ordine
  7. cancellazione ultimo elemento
  8. inserimento in lista ordinata
  9. non in programma: il metodo del puntatore a puntatore

Tutto il capitolo su una pagina   Versione postscript   Versione PDF