Le funzioni Ricorsive

Le funzioni ricorsive hanno fatto la loro comparsa sulla scena molto tempo fa'. Praticamente con il primo linguaggio che era dotato di funzioni.

Cosa e' una funzione ricorsiva? In sostanza si tratta di una funzione che, per svolgere il proprio lavoro, richiama se' stessa. Ad ogni richiamo la "profondita'" dell'elaborazione aumenta, finche' ad un certo punto, lo scopo viene raggiunto e la funzione ritorna.

Il tipico esempio di una funzione Ricorsiva e' la visualizzazione di dati in strutture gerarchiche, per esempio la visualizzazione dei file contenuti in una directory.

Invece di scervellarsi per trovare un sistema che 'visiti' ogni sotto-directory presente, si crea una funzione 'generica' che legge una directory e visualizza ogni file. Se il file e' una directory, la funzione richiama se' stessa usando la directory trovata come parametro.

Lo pseudo codice qui' sotto esemplifica questo funzionamento:

Function leggi_directory( directory_iniziale )
{
  for each File in [directory_iniziale] {
    if (file_normale(File)) {
      stampa_nome_file(File);
    } else {
      leggi_directory( File ); // ricorsione
    }
  Next;
}

Se File e' riconosciuto come una directory, la funzione richiama se' stessa per analizzare il contenuto della directory stessa.

Questa logica ovviamente non tiene conto di possibili problemi (la presenza di link per esempio).

Sicuramente il codice in questo caso e' molto semplice, ma la domanda e': questo codice e' efficiente?

Per cominciare a progettare una funzione ricorsiva, occorre pensare se il "lavoro" da svolgere puo' essere spezzato in una sequenza di mini-operazioni identiche. Inoltre occorre pensare a quando la singola operazione dovra' concludersi e ritornare.

La regola base di una funzione ricorsiva e' che nessuno stato, valore o condizione che non sia controllato dalla funzione stessa deve essere modificato. In caso contrario la ricorsione non funzionera' come ci si aspetta.

Che significa questo? Riprendiamo l'esempio della lettura directory di poco fa'. Nel nostro caso abbiamo un'elenco di file/directory e leggiamo un elemento alla volta. Se troviamo una directory, richiamiamo la funzione che riceve un nuovo elenco di file/directory da leggere.

Tutto questo e' OK perche' l'elenco precedente non viene toccato, ma se (per struttura interna del sistema), la lettura del nuovo elenco distrugge (o modifica) l'elenco precedente, la ricorsione non funziona piu'. Dopo il primo richiamo la funzione che ritorna si ritrova con l'elenco che stava leggendo modificato o (peggio) distruttor. Probabilmente riceveremo un errore.

Perche' il nostro algoritmo possa funzionare in queste condizioni e' necessario salvare lo stato della funzione prima del richiamo e ripristinarlo dopo. Questo complica il funzionamento della nostra routine e ci obbliga a scrivere del codice aggiuntivo.

Una funzione ricorsiva "salva" il suo stato nel momento in cui richiama se' stessa, solitamente nello stack. Ogni volta che la ricorsione viene invocata, tutte le variabili presenti vengono inserite nello stack ed una nuova serie di variabili viene creata (sempre dallo stack).

Questo significa un elevato consumo dello stack del sistema, se stiamo lavorando con uno stack limitato (come e' il caso con certi sistemi o con certe architetture di programma), rischiamo di superare i limiti dello stack e di avere un bel crash del programma.

Aggiungiamo poi che, solitamente, il numero di chiamate ricorsive della funzione non e' ipotizzabile a priori ed abbiamo un possibile problema.

Un altro possibile problema e' se la nostra funzione utilizza altre risorse oltre alla memoria del sistema, e tali risorse sono in quantita' limitata (connessioni a database per esempio). In questo caso, se il numero di richiami e' superiore ad un certo livello, possiamo avere un fallimento di chiamata.

Non sempre le funzioni ricorsive sono una risposta efficiente. Consideriamo che ogni chiamata ricorsiva consuma memoria ed utilizza un salto ad una funzione. Ridisegnando la funzione come non-ricorsiva, si risparmia un salto e (forse) un po' di quella preziosa memoria.

Sfortunatamente, non tutte le funzioni sono facilmente 'trasformabili' da ricorsive a non-ricorsive, in alcuni casi la funzione non puo' essere trasformata senza una completa riscrittura, e non sempre ne vale la pena.

L'algoritmo di ricerca in un albero binario e' il primo tipo di funzione ricorsiva che solitamente si analizza. Un albero binario e' una struttura logica in cui ogni singolo elemento (nodo) ha due collegamenti ad altrettanti nodi. Un albero e' detto "bilanciato", quando tutti gli elementi dell'ultima riga non hanno nessun collegamento.

Gli alberi binari sono utilizzati per implementare indici e funzioni di ricerca/ordinamento.

Nel nostro caso si assume che l'albero e' costruito in modo tale che il nodo a sinistra e' minore della 'radice', mentre il nodo a destra e' maggiore.

La funzione che analizza l'albero in cerca di un valore puo' essere scritta con la ricorsione in modo molto semplice. Ci sono due casi in cui la funzione deve ritornare: il primo caso e' quando il nodo e' identico a quello cercato, il secondo caso e' quando il nodo non ha nessun 'figlio', cioe' quello che cerchiamo non e' qui'.

La funzione ricorsiva puo' essere scritta come segue:

cerca_nodo( nodo, valore )
{
  if( nodo = -1 || valore == albero[nodo] )
    return nodo;
  if( valore < albero[nodo] )
    return cerca_nodo( albero[nodo].sinistro, valore );
  else
    return cerca_nodo( albero[nodo].destro, valore );
}

Se il nodo-figlio (destro o sinistro) non ha valore (il nodo-radice non ha figli), il valore ritornato e' -1.

Questo tipo di codifica gestisce efficientemente la ricerca in alberi binari anche complessi, il problema e' appunto l'utilizzo di risorse per gestire la ricorsione.

Il consumo di stack dell'algoritmo dipende pesantemente da quanto bilanciato e' l'albero. Se l'abero e' perfettamente bilanciato, per localizzare un qualunque nodo sono richiesti meno di log2(n) ricerche, dove n e' il numero di elementi dell'albero. Per un albero di 65.000 elementi sono necessarie solo 16 iterazioni. L'impatto sullo stack in questo caso e' minimo.

Nel caso di un albero molto sbilanciato, il nostro algoritmo non si comporta altrettanto bene, potrebbe essere necessario in questo caso il controllo di ogni singolo nodo dell'albero.

Trasformare la ricerca binaria in un algoritmo non-ricorsivo e' un lavoro abbastanza semplice. Il nostro algoritmo infatti non richiede espressamente la ricorsione. La funzione ritorna in due soli casi: ho ha trovato il nodo o non lo ha trovato. Non c'e' motivo di "ritornare all'inizio".

L'uso di una funzione non-ricorsiva in questo caso rimuove il consumo extra di memoria e rende la funziona anche piu' veloce.

Una chiamata ricorsiva effettua due operazioni: (1) prepara le variabili per la chiamata successiva e (2) ritorna all'inizio.

Nel nostro caso (1) puo' essere facilmente fatto modificando il valori di node con il nuovo nodo da esaminare, mentre (2) puo' essere effettuato usando un salto incondizionato (goto) o un qualche tipo di ciclo.

Il codice dell'algoritmo non-ricorsivo e' il seguente:

cerca_nodo( nodo, valore )
{
  /* ciclo infinito */
  while(1) {
    if( nodo = -1 || valore == albero[nodo] )
      break;
    if( valore < albero[nodo] )
      nodo = albero[nodo].sinistro;
    else
      nodo = albero[nodo].destro;
  }
  return nodo;
}

Algoritmi piu' complessi possono essere un problema da convertire. Prendiamo ad esempio la nostra funzione di 'scorrimento' delle directory. Il problema e' che dobbiamo salvare da qualche parte l'elenco dei file che stiamo gestendo e la posizione all'interno prima di ritornare all'inizio e processare il nuovo elenco, perche' al termine di questo dovremo ritornare indietro e procedere come se niente fosse successo.

La domanda e' dove accidenti salvo questa roba?. La risposta e' bisogna implementare un sistema di stack.

Ma se usiamo un altro stack, dove sta' il vantaggio di eliminare la ricorsione?

Un primo vantaggio e' che lo stack puo' essere molto piu' grande di quello di sistema, un secondo vantaggio e' che siamo in grado di controllarne la dimensione e la crescita, ed eventualmente di bloccare il processo se questo cresce eccessivamente.

Il nostro algoritmo di scorrimento directory non-ricorsivo, potrebbe essere qualche cosa come il seguente:

Function leggi_directory( directory_iniziale )
{

:ciclo

  for each File in [directory_iniziale] {

:riprendi
  
    if (file_normale(File)) {
      stampa_nome_file(File);
    } else {
      /* inserisco gli elementi nello stack */
      inserisci_stack( directory_iniziale );
      inserisci_stack( File );
      directory_iniziale = File;
      goto ciclo;
    }
  }

  /* verifico di non aver esaurito lo stack */
  if( stack_esaurito() ) {
    return;
  } else {
    /* prelevo gli elementi precedenti dallo stack */
    File = estrai_stack();
    directory_iniziale = estrai_stack();
    goto riprendi;
  }

}

N.B. L'uso dei goto in questo codice, benche' eliminabile, consente di avere un codice piu' comprensibile. Una stesura del codice senza i goto richiede la scrittura di piu' subroutine o l'uso di cicli infiniti piuttosto intricati.

Gli algoritmi ricorsivi sono veloci da scrivere, ma non sempre cosi' efficienti, in moltissimi casi l'uso di un algoritmo equivalente ma non-ricorsivo permette una maggiore efficienza al prezzo di un po' di codice in piu' da scrivere. Soprattutto se il codice stesso richiede l'uso di uno Stack per tenere traccia dello stato precedente dell'iterazione.

I commenti sono aggiunti quando e soprattutto se ho il tempo di guardarli e dopo aver eliminato le cagate, spam, tentativi di phishing et similia. Quindi non trattenete il respiro.

1 messaggio this document does not accept new posts

---

Di zoninoz postato il 03/08/2013 20:44

---

Precedente Successivo

Davide Bianchi, lavora come Unix/Linux System Administrator presso una societa' di Hosting in Olanda.

Volete contribuire? Leggete come!.
 
 

Il presente sito e' frutto del sudore della mia fronte (e delle mie dita), se siete interessati a ripubblicare uno degli articoli, documenti o qualunque altra cosa presente in questo sito per cortesia datemene comunicazione (o all'autore dell'articolo se non sono io), cosi' il giorno che faccio delle aggiunte potro' avvisarvi e magari mandarvi il testo aggiornato.