Le funzioni Ricorsive

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;
}

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?

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.

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.

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.

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 );
}

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.

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;
}

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;
  }

}

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.

Previous Next