Struttura dei dati - Nozioni di base sulla ricorsione

Alcuni linguaggi di programmazione per computer consentono a un modulo o una funzione di chiamare se stesso. Questa tecnica è nota come ricorsione. Nella ricorsione, una funzioneα o chiama se stesso direttamente o chiama una funzione β che a sua volta chiama la funzione originale α. La funzioneα è chiamata funzione ricorsiva.

Example - una funzione che chiama se stessa.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - una funzione che chiama un'altra funzione che a sua volta la chiama di nuovo.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Proprietà

Una funzione ricorsiva può diventare infinita come un ciclo. Per evitare l'esecuzione infinita della funzione ricorsiva, ci sono due proprietà che una funzione ricorsiva deve avere:

• Base criteria - Deve esserci almeno un criterio o condizione di base, tale che, quando questa condizione è soddisfatta, la funzione smetta di chiamarsi ricorsivamente.

• Progressive approach - Le chiamate ricorsive dovrebbero progredire in modo tale che ogni volta che viene effettuata una chiamata ricorsiva, si avvicini ai criteri di base.

Implementazione

Molti linguaggi di programmazione implementano la ricorsione tramite stacks. In genere, ogni volta che una funzione (caller) chiama un'altra funzione (callee) o se stessa come chiamato, la funzione chiamante trasferisce il controllo dell'esecuzione al chiamato. Questo processo di trasferimento può anche comportare il trasferimento di alcuni dati dal chiamante al chiamato.

Ciò implica che la funzione chiamante deve sospendere temporaneamente la sua esecuzione e riprenderla in seguito quando il controllo dell'esecuzione ritorna dalla funzione chiamata. In questo caso, la funzione chiamante deve iniziare esattamente dal punto di esecuzione in cui si mette in attesa. Ha anche bisogno degli stessi identici valori di dati su cui stava lavorando. A tale scopo, viene creato un record di attivazione (o stack frame) per la funzione chiamante.

Questo record di attivazione conserva le informazioni sulle variabili locali, i parametri formali, l'indirizzo di ritorno e tutte le informazioni passate alla funzione chiamante.

Analisi della ricorsione

Si potrebbe discutere il motivo per cui utilizzare la ricorsione, poiché la stessa attività può essere eseguita con l'iterazione. Il primo motivo è che la ricorsione rende un programma più leggibile e grazie ai più recenti sistemi CPU avanzati, la ricorsione è più efficiente delle iterazioni.

Complessità temporale

In caso di iterazioni, prendiamo il numero di iterazioni per contare la complessità temporale. Allo stesso modo, in caso di ricorsione, assumendo che tutto sia costante, proviamo a calcolare il numero di volte in cui viene effettuata una chiamata ricorsiva. Una chiamata fatta a una funzione è Ο (1), quindi il numero (n) di volte che viene fatta una chiamata ricorsiva rende la funzione ricorsiva Ο (n).

Complessità spaziale

La complessità dello spazio viene conteggiata come la quantità di spazio extra necessaria per l'esecuzione di un modulo. In caso di iterazioni, il compilatore non richiede quasi alcuno spazio aggiuntivo. Il compilatore continua ad aggiornare i valori delle variabili utilizzate nelle iterazioni. Ma in caso di ricorsione, il sistema deve memorizzare il record di attivazione ogni volta che viene effettuata una chiamata ricorsiva. Quindi, si ritiene che la complessità spaziale della funzione ricorsiva possa essere superiore a quella di una funzione con iterazione.