Fibonacci: Chiamate ricorsive
Data la funzione ricorsiva che calcola l'n-esimo numero di Fibonacci:
voglio calcolare quante chiamate ricorsive ci sono nell'albero di ricorsione. Empiricamente osservando gli alberi di ricorsione per alcuni n, ho trovato una formula generale, che è sempre verificata. La formula è la seguente: $sum_{k=1}^n fib(k) + fib(n-1)$.
Volevo sapere se è possibile, utilizzando magari le relazioni di ricorrenza, arrivare per altra via alla formula.
Accetto ogni suggerimento (utile!).
Ciao!
int fib(int n)
{
if (n==0)
return 0;
else if (n==1)
return 1;
else
return (fib(n-1)+fib(n-2));
}
voglio calcolare quante chiamate ricorsive ci sono nell'albero di ricorsione. Empiricamente osservando gli alberi di ricorsione per alcuni n, ho trovato una formula generale, che è sempre verificata. La formula è la seguente: $sum_{k=1}^n fib(k) + fib(n-1)$.
Volevo sapere se è possibile, utilizzando magari le relazioni di ricorrenza, arrivare per altra via alla formula.
Accetto ogni suggerimento (utile!).
Ciao!
Risposte
Ho trovato la relazione di ricorrenza. Il numero di chiamate ricorsive è pari a $2Fib(n+1)-1$. Grazie lo stesso a chi si è interessato (se ci sono!)
Ciao!
Ciao!
io la successione di fibonacci la facevo in un altro modo...
cioè mettevo prima 1
poi un altro 1
poi iniziavo a calcolare il primo piu il secondo, sostituivo il secondo al primo e cosi via di somme... non so se è quello che hai fatto tu...
cioè mettevo prima 1
poi un altro 1
poi iniziavo a calcolare il primo piu il secondo, sostituivo il secondo al primo e cosi via di somme... non so se è quello che hai fatto tu...
si, lui ha fatto la stessa cosa, ma in linguaggio C 
"eafkuor":
si, lui ha fatto la stessa cosa, ma in linguaggio C
La successione di Fibonacci non è definita in base al linguaggio di programmazione!!!
Infatti essa è definita ricorsivamente: ${(F_0=0),(F_1=1),(F_n=F_{n-1}+F_{n-2}):}$
appunto. Io però l'ho implementata in modo diverso... 
"superpunk733":
appunto. Io però l'ho implementata in modo diverso...
Secondo me la tua implementazione è errata, e non rispetta la definizione. Ma a parte questo non capisco quale sia il nesso fra definizione e linguaggio di programmazione introdotto da eafkuor.
guarda la mia implementazione funziona... ho capito cos'è: tu hai fatto una funzione che contiene due funzioni (mi pare), mentre io ho fatto una cosa piu diretta... quando sto su linux la mando, cmq funziona...
"superpunk733":
guarda la mia implementazione funziona... ho capito cos'è: tu hai fatto una funzione che contiene due funzioni (mi pare), mentre io ho fatto una cosa piu diretta... quando sto su linux la mando, cmq funziona...
Voglio sapere una sola cosa allora: se passi come parametro alla funzione il valore zero che ti restituisce?
io NON ho fatto una funzione 
era uno dei primi programmi c++ che facevo e lho fatto semplicemente con un for
era uno dei primi programmi c++ che facevo e lho fatto semplicemente con un for
"superpunk733":
io NON ho fatto una funzione
Ma allora non hai utilizzato la ricorsione. Non vedo il nesso in questo topic!
"leonardo":
Infatti essa è definita ricorsivamente: ${(F_0=0),(F_1=1),(F_n=F_{n-1}+F_{n-2}):}$
Bè la funzione fib() da te definita non è un po' la stessa cosa?
"eafkuor":
[quote="leonardo"]
Infatti essa è definita ricorsivamente: ${(F_0=0),(F_1=1),(F_n=F_{n-1}+F_{n-2}):}$
Bè la funzione fib() da te definita non è un po' la stessa cosa?
[/quote]Guarda che è la stessa cosa e lo deve essere!
Quella di cui parlate voi non è la vera definizione della successione di Fibonacci!
Allora, superpunk733 ha detto questo:
e io ho semplicemente detto che "si, è quello che ha fatto lui, in linguaggio C". Tutto qui
"superpunk733":
poi iniziavo a calcolare il primo piu il secondo, sostituivo il secondo al primo e cosi via di somme... non so se è quello che hai fatto tu...
e io ho semplicemente detto che "si, è quello che ha fatto lui, in linguaggio C". Tutto qui
La funzione di Fibonacci può essere implentata sia in modo ricorsivo (tenendo fede alla definizione stessa della funzione) sia in modo iterativo.
Solo una cosa a Leonardo: non ritieni che sia più leggibile far riferimento ai canoni della programmazione struttura? Ossia: non sarebbe meglio usare un solo punto di uscita return, e sostituire i tre return nella cascata if-else con una variabile che contenga l'eventuale valore da restituire?
Te lo dico solo perchè a me hanno insegnato sempre ad usare la programmazione struttura e non conosco nè pregi nè vantaggi del sistema usato da te (con più punti di uscita).
Ciao
Spartaco
Solo una cosa a Leonardo: non ritieni che sia più leggibile far riferimento ai canoni della programmazione struttura? Ossia: non sarebbe meglio usare un solo punto di uscita return, e sostituire i tre return nella cascata if-else con una variabile che contenga l'eventuale valore da restituire?
Te lo dico solo perchè a me hanno insegnato sempre ad usare la programmazione struttura e non conosco nè pregi nè vantaggi del sistema usato da te (con più punti di uscita).
Ciao
Spartaco
"Enea":
La funzione di Fibonacci può essere implentata sia in modo ricorsivo (tenendo fede alla definizione stessa della funzione) sia in modo iterativo.
Solo una cosa a Leonardo: non ritieni che sia più leggibile far riferimento ai canoni della programmazione struttura? Ossia: non sarebbe meglio usare un solo punto di uscita return, e sostituire i tre return nella cascata if-else con una variabile che contenga l'eventuale valore da restituire?
Te lo dico solo perchè a me hanno insegnato sempre ad usare la programmazione struttura e non conosco nè pregi nè vantaggi del sistema usato da te (con più punti di uscita).
Ciao
Spartaco
Io ho sempre saputo "Programmazione strutturata". A parte il problema di notazione/nomenclatura dei tipi/paradigmi della programmazione, una funzione in linguaggio C scritta nel modo da me sopra utilizzato è una semplice funzione di tipo int, che restituisce un qualsiasi valore tramite l'istruzione return. L'istruzione return infatti permette di restituire alla funzione chiamante un valore di tipo predefinito nel prototipo della funzione, tramite un usage definito a priori. Di solito, come nel mio caso, in una funzione basta eseguire un'istruzione del tipo "f=fib(n)", con f una variabile dello stesso tipo o magari un tipo più grande (viene automaticamente al tipo più grande, ad esempio fib è int e f float, il valore restituito dalla chiamata fib(n) viene promosso automaticamente a float), e n una variabile int, come è leggibile dal prototipo della funzione. Spero di essere stato esaustivo. Per altre domande/chiarimenti riguardo alla questione citata, chiedi pure!
Ciao!
"leonardo":
[quote="eafkuor"][quote="leonardo"]
Infatti essa è definita ricorsivamente: ${(F_0=0),(F_1=1),(F_n=F_{n-1}+F_{n-2}):}$
Bè la funzione fib() da te definita non è un po' la stessa cosa?
[/quote]Guarda che è la stessa cosa e lo deve essere!
Quella di cui parlate voi non è la vera definizione della successione di Fibonacci![/quote]
Assolutamente vero. E' solo un metodo poco ortodosso per ottenerla.
Io ho sempre saputo "Programmazione strutturata".
Si, scusa, intendevo quello ma ho scritto male... lapsus.
programmazione, una funzione in linguaggio C scritta nel modo da me sopra utilizzato è una semplice funzione di tipo int, che restituisce un qualsiasi valore tramite l'istruzione return. L'istruzione return infatti permette di restituire alla funzione chiamante un valore di tipo predefinito nel prototipo della funzione, tramite un usage definito a priori. Di solito, come nel mio caso, in una funzione basta eseguire un'istruzione del tipo "f=fib(n)", con f una variabile dello stesso tipo o magari un tipo più grande (viene automaticamente al tipo più grande, ad esempio fib è int e f float, il valore restituito dalla chiamata fib(n) viene promosso automaticamente a float), e n una variabile int, come è leggibile dal prototipo della funzione. Spero di essere stato esaustivo. Per altre domande/chiarimenti riguardo alla questione citata, chiedi pure!
Si si, questo è chiaro. Quello che ti chiedevo io era soltanto un tuo personale giudizio sul paradigma della programmazione strutturata e su un eventuale aumento di leggibilità (e forse anche altre qualità) di un algoritmo con una sola istruzione return (e quindi un unico punto di uscita, come nei canoni della programmazione strutturata).
Grazie mille dell'interesse
Ciao
Enea
"Crook":
Assolutamente vero. E' solo un metodo poco ortodosso per ottenerla.
Di quale metodo parli???
"Enea":
Si si, questo è chiaro. Quello che ti chiedevo io era soltanto un tuo personale giudizio sul paradigma della programmazione strutturata e su un eventuale aumento di leggibilità (e forse anche altre qualità) di un algoritmo con una sola istruzione return (e quindi un unico punto di uscita, come nei canoni della programmazione strutturata).
Grazie mille dell'interesse
Ciao
Enea
La funzione fib così scritta non può essere migliorata ulteriormente perchè rispecchia in modo univoco la definizione ricorsiva della successione di Fibonacci. Non capisco cosa voglio dire "algoritmo con una sola istruzione return": in questo caso, come in moltissimi altri casi, i "punti di uscita" sono moltissimi e diversi tra loro, e quindi non raggruppabili. Poi non vedo il bisogno di raggruppare più return, limiterebbe molto spesso la potenza di una funzione.
Ciao!
La funzione fib così scritta non può essere migliorata ulteriormente perchè rispecchia in modo univoco la definizione ricorsiva della successione di Fibonacci. Non capisco cosa voglio dire "algoritmo con una sola istruzione return"
int fib(int n)
{
int f;
if (n==0)
f=0;
else if (n==1)
f=1;
else
f=(fib(n-1)+fib(n-2));
return f;
}
Intendevo questo; un solo punto di uscita, come vogliono i canoni della programmazione strutturata.
Ti chiedevo un tuo giudizio al riguardo.
in questo caso, come in moltissimi altri casi, i "punti di uscita" sono moltissimi e diversi tra loro, e quindi non raggruppabili. Poi non vedo il bisogno di raggruppare più return, limiterebbe molto spesso la potenza di una funzione.
Ora ho capito il tuo punto di vista.
Grazie
Ciao
Enea
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo