Ricorsione di fibonacci

di
max1990
il
6 risposte
M
max1990
Pochi posts
Iscritto da
gen, 2011
Messaggi:
27

Ricorsione di fibonacci

Ciao a tutti qualcuno sa spiegarmi quante invocazioni di funzioni ci sono nel calcolo di fibonacci di 3 _(ricorsivamente)e quanti per fibonacci di 4.
grazie
l esercizio e questo:

int fib(int i) {
int res;
if (i>1)
res = fib(i-1)+fib(i-2);
else if (i == 1)
res = 1;
else
res = 0;
return res;
}

6 Risposte

  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricorsione di fibonacci

    
static int numChiamate = 0;

int fib(int i) {
numChiamate++;
int res;
if (i>1)
res = fib(i-1)+fib(i-2);
else if (i == 1)
res = 1;
else
res = 0;
return res;
}

printf("Numero invocazioni alla funzione = %d",numChiamate);
    Usa il compilatore e trovalo. Vedrai che dopo un po di prove troverai la formula generalizzata.
  • Bomberdini
    Bomberdini
    Molto attivo
    Iscritto da
    feb, 2011
    Messaggi:
    527

    Re: Ricorsione di fibonacci

    Fibonacci di 4 fa scaturire le seguenti funzioni:

    fibonacci(3) -- fibonacci(2)

    fibonacci(2) -- fibonacci(1)

    Mentre fibonacci di 3 fa scaturire le seguenti funzioni:

    fibonacci (2) -- fibonacci(1)
  • M
    max1990
    Pochi posts
    Iscritto da
    gen, 2011
    Messaggi:
    27

    Re: Ricorsione di fibonacci

    Per skynet non riesco a far funzionare il programma la funzione anche se cambio il valore di i mi da sempre zero
  • M
    max1990
    Pochi posts
    Iscritto da
    gen, 2011
    Messaggi:
    27

    Re: Ricorsione di fibonacci

    Per Bomberdini sbaglio se dico che fibonacci di 5 fa scaturire
    fib 4 e fib di 3
    fib 3 e fib di 2
    fib di 2 e fib di 1??
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricorsione di fibonacci

    
#include <stdio.h>
#include <stdlib.h>


static int numChiamate = 0;

int fib(int i) 
{
	int res;
	numChiamate++;
	if (i>1)
		res = fib(i-1)+fib(i-2);
	else if (i == 1)
		res = 1;
	else
		res = 0;
	return res;
}
int main()
{
	fib(3);
	printf("Numero invocazioni alla funzione = %d",numChiamate);
	return 0;
}
  • Bomberdini
    Bomberdini
    Molto attivo
    Iscritto da
    feb, 2011
    Messaggi:
    527

    Re: Ricorsione di fibonacci

    In realta fibonacci di 5 scaturisce le seguenti chiamate:

    Fib(5)
    Fib(4) Fib(3)
    Fib(3) Fib(2) Fib(2) Fib(1)
    Fib(2) Fib(1)

    e da qui si vede chiaramente che Fibonacci ricorsivo non è efficiente perchè richiama piu volte funzioni gia chiamate prima come (Fib(3) ; Fib(2) ; Fib(1))
Devi accedere o registrarti per scrivere nel forum
6 risposte