Informatica: la programmazione ricorsiva



La ricorsione è una delle tecniche di programmazione meno conosciute, ma più potenti, specialmente in certe tipologie di calcolo che necessitano di passi ‘ripetuti‘.
Dal punto di vista informatico consiste in una funzione (routine, subroutine, … dipende dal linguaggio) che al suo interno effettua un richiamo a se stessa.

Le funzioni ricorsive devono SEMPRE avere un meccanismo che, ad un certo punto, blocchi la ricorsione per evitare ‘loop‘ senza fine che bloccherebbero o manderebbero in errore il programma (i moderni Sistemi Operativi hanno dei controlli interni per evitare che questo succeda e generano un errore quando si supera il numero massimo di ricorsioni o lo spazio riservato all’esecuzione della funzione si esaurisce).

Usiamo per il nostro esempio Javascript (di potete vedere sul sito www.abspace.it/ComputerSpace/JavascriptCheatSheet.asp  per una guida breve alle funzionalità), che è facilmente inseribile all’interno di una semplice pagina HTML ed attivabile su qualsiasi computer (e, tra l’altro, non richiede compilazioni).

Iniziamo quindi creando una funzione che esegua una qualsiasi potenza di un numero dato, cioè che risolva potenze come le seguenti: 2<sup>3</sup> o 4<sup>2</sup>.
Quindi la nostra funzione avrà due parametri: il numero della base ed il numero dell’esponente, esempio:

potenzaNormale( base, esponente )

Ecco l’implementazione più semplice:

function potenzaNormale( base, esponente )
{
var risultato;
risultato = 1;
for( i=esponente;i>0;i--)
risultato = risultato * base;   //si può scrivere anche: base *= base;
return risultato;
}

Quindi chiamando la funzione:

potenza = potenzaNormale( 2, 3 );

e stampando il risultato con:

document.write( "Risultato:" + potenza );

otterremo il nostro numero 8.

Ovviamente la nostra funzione è perfetta esegue perfettamente il calcolo, ma proviamo a renderla ora ricorsiva con poche modifiche:

function potenzaRicorsiva( base, esponente )
{
// se la base è 0 non esegue nessuna ricorsione e ritorna 0
if (base == 0) return( 0 );
// se l'esponente è 0 non esegue nessuna ricorsione e ritorna 1
else if (esponente == 0) return( 1 );
// negli altri casi esegue la chiamata ricorsiva
else return ( base * potenzaRicorsiva( base, esponente-1 ) );
}

Come vedere il ciclo di ripezione è stato stostituito dalla chiamata ricorsiva che ne riproduce il funzionamento.

Concluendo le funzioni ricorsive sono molto potenti, ma si deve avere sempre sotto controllo il numero di iterazioni (cioè il numero di chiamate a se stessa) che non deve mai essere fuori controllo.
Per esempio se nella nostra pagina demo mettiamo un esponente troppo alto, e quindi aumentiamo il numero di chiamate ricorsive, avremo sicuramente un errore, per esempio Firefox, usando come esponente 10000, indica l’errore “too mush recursion”:

Personalmente trovo la programmazione ricorsiva uno strumento potente ed al contempo molto elegante (programmaticamente parlando ovviamente) e mi auguro che questo piccolo esempio serva a chiarirne l’utilizzo.

Per concludere di seguito il codice completo della nostra pagina web che ci consentirà di provare le nostre funzioni.

Alberto Bellina


<html><head>
<title>La ricorsione nell'elevamento a potenza</title>
<script language="javascript" type="text/javascript">
function potenzaNormale( base, esponente )
{
var risultato;
risultato = 1;
for( i=esponente;i>0;i--)
risultato = risultato * base;   //si può scrivere anche: base *= base;
return risultato;
}

function potenzaRicorsiva(base, esponente)
{
if (base == 0) return( 0 );
else if (esponente == 0) return( 1 );
else return ( base * potenzaRicorsiva( base, esponente-1 ) );
}

function eseguiNormale()
{
var base      = parseInt(document.form_a.base.value);
var esponente = parseInt(document.form_a.esponente.value);
var potenza   = potenzaNormale( base, esponente );
document.form_a.potenza.value = potenza;
document.form_a.tipopotenza.value = "normale";
}

function eseguiRicorsiva()
{
var base      = parseInt(document.form_a.base.value);
var esponente = parseInt(document.form_a.esponente.value);
var potenza   = potenzaRicorsiva( base, esponente );
document.form_a.potenza.value = potenza;
document.form_a.tipopotenza.value = "ricorsiva";
}

</script>
</head>
<body>
<b>Elevamento a potenza di valori positivi interi</b><br>
<form name="form_a" method="get" action="">
base      = <input type="text" size="10" name="base"><br>
esponente = <input type="text" size="10" name="esponente"><br>
potenza   = <input type="text" size="10" name="potenza" value="0">
tipo funzione   = <input type="text" size="10" name="tipopotenza" value="0"><br>
<input type="button" value="eseguinormale" onclick="eseguiNormale()"><br>
<input type="button" value="eseguiricorsiva" onclick="eseguiRicorsiva()"><br>
</form>
</body>
</html>

Annunci sponsorizzati:
Condividi su Facebook Condividi su Twitter!
Pinterest