PDA

Visualizza versione completa : [C] Ricorsività


Downloader
09-11-2007, 11.59.01
Avrei bisogno di un aiutino per capire al meglio il concetto di ricorsività, visto che questo per me è un argomento davvero ostico in quanto non l'ho mai affrontato.

Vedo che chi usa la ricorsività a meno di grossi problemi da risolvere vede globalmente tutto il problema molto semplicemente e lo risolve con una riga di codice.
Forse (anzi sicuramente) sbaglierò io nell'analizzare quello che una funzione ricorsiva deve fare, ma io per ora anche solo per capire come funziona la ricorsività devo farmi tutte le operazioni e le chiamate che fa lei, e questo oltre ad essere poco una operazione poco agevole e molto lenta non in tutti i casi porta buoni risultati.


Cosa potete dirmi??



tnx!

LoryOne
09-11-2007, 12.18.35
Quando il risultato di una funzione parametrica diventa il parametro passato alla funzione stessa, tale funzione si dice ricorsiva.
Il calcolo del fattoriale di un numero o la ricerca di sottocartelle di un hard disk sono entrambe funzionalità ricorsive.
E' come dire che una funzione fa ricorso a se stessa un numero x di volte per ottenere il rusltato sperato.

Downloader
09-11-2007, 12.26.08
Il problema che ho a volte studiando dei codici è proprio capire come fa una funzione a restituire un certo valore quando quel valore deve essere sommato ad un'altra funzione ricorsiva.

Poco chiaro eh?

Ecco un esempio che mi sta facendo impazzire:

int fibo(int n)
{
if (n < 2)
return n;
else
return fibo(n-1) + fibo(n-2);
}


Questa funzione come si sarà capito calcola l'nesimo numeri di Fibonacci.
Ma...se iterativamente si risolve facilmente, ricorsivamente invece mi fa fumare il cervello per via dei valori intermedi che le due funzioni ricorsive generano.

Ora siccome credo che sia pazzia per tutti mettersi a calcolare ogni ambiente di funzione che risultato restituisce mi chiedevo se c'era una maniera di riuscire ad arrivare a scrivere il codice in maniera decisamente più veloce senza gli impazzimenti dei calcoli.

Thor
09-11-2007, 12.30.07
Se cerchi "ricorsione" su google trovi un sacco di roba
Una funzione ricorsiva, per svolgere il proprio lavoro, richiama sè stessa più volte, aumentando di volta in volta la profondità dell'elaborazione

ad es. il fattoriale, classico


#include <stdio.h>

int fattoriale(unsigned int n);

main(void)
{ int n;
printf("\nIntroduci N:\t");
scanf("%d",&n);
printf("\nIl fattoriale di %d è \t%d\n", n, fattoriale(n));
}

int fattoriale(unsigned int n)
{
if (n==0 || n==1) return 1
else return n*fattoriale(n-1); /*ricorsione*/
}

se invece lo faccio in versione iterativa, cambia la funzione:

int fattoriale(unsigned int n)
{
int tmp, f=1;
for (tmp=1; tmp<=n; tmp++)
f *= tmp;
return f;
}

Downloader
09-11-2007, 12.33.41
Ho già "googolato", ma non ho trovato una risposta alla mia domanda, o forse l'ho trovata ma non l'ho trovata esauriente, o forse non l'ho capita.

Che una funzione ricorsiva chiami se stessa è chiaro a tutti, non mi è chiaro però come funzionino certi meccanismi ad esempio nel codice che ho postato sopra.

Thor
09-11-2007, 12.36.26
be', se chiedi se esista una regola generale per scrivere funzioni ricorsive, la risposta è no..sei tu che tramite astrazione mentale, devi riuscire a tirar fuori un procedimento che può chiamare sè stesso per risolvere il problema.

proprio come per fibonacci. quella è ricorsione non lineare, sono certo che altri tipi di ricorsione, come quello che ho scritto io su, ti vengano più facili, no?

Downloader
09-11-2007, 12.41.56
be', se chiedi se esista una regola generale per scrivere funzioni ricorsive, la risposta è no..sei tu che tramite astrazione mentale, devi riuscire a tirar fuori un procedimento che può chiamare sè stesso per risolvere il problema.

proprio come per fibonacci. quella è ricorsione non lineare, sono certo che altri tipi di ricorsione, come quello che ho scritto io su, ti vengano più facili, no?

Infatti, con quelli non ho particolari problemi, perchè comunque sia bene o male riesco ad immaginare quello che devono fare.

Thor
09-11-2007, 12.43.16
Comunque sia, la definizione della funzione di fibonacci, se non sbaglio, è proprio:
F0= 0; F1= 1; Fn = F(n-1) + F(n-2), con F0 aggiunto se si vuol far partire la successione con 0.
Dunque proprio la versione "ricorsiva" che si scrive.

http://it.wikipedia.org/wiki/Successione_di_Fibonacci

LoryOne
09-11-2007, 16.09.00
Effettivamente è piuttosto difficile riuscire a spiegare il concetto.
Cominciamo dalle cose semplici: il fattoriale di 5 è 120
E' come se l'operazione di moltiplicazione fosse da intendersi in questo modo: 5*4*3*2*1
Si può ottenere lo stesso risultato in questo modo: 5*1*2*3*4
In entrambi i casi, ci si ferma dopo 5-1 volte, cioè dopo 4 moltiplicazioni: 4 è dato infatti da 5-1
Lo scopo principale di una funzione ricorsiva è sapere quante volte è necessario iterare fino a fermarsi; Fermarsi è il punto.
Ogni funzione genera al suo interno una serie di operazioni, ma termina quando il risultato delle operazioni è un numero finito, non il risultato di un' ulteriore operazione algebrica.
Il return a meno che non lo si forzi a restituire 0 si aspetta sempre un valore positivo il più vicino possibile a zero.
Nel nostro caso, n*fattoriale(n-1) si fermerà quando (n-1) sarà uguale a 1
5*(5-1)=20
20*(4-1)=60
60*(3-1)=120
120*(2-1)=120
Sono 4 le operazioni e 2-1=1. ;)
Perdonatemi matematici, ma io sono terra-terra quando spiego. :-(

LoryOne
09-11-2007, 16.17.46
Ti faccio notare che anche la funzione iterativa si ferma e tu sai bene quando:
for (tmp=1; tmp<=n; tmp++)