Dubbio su ricorsione

di il
7 risposte

Dubbio su ricorsione

Dunque, sono un attimo in difficoltà con la comprensione di alcuni passaggi che riguardano un programma ricorsivo.

Esposizione:

La ricorsione prevede che all'interno della funzione ricorsiva, sia generata una chiamata ricorsiva (o passo ricorsivo) in modo da suddividere un caso piu complesso, rispetto a quello base, in modo da far convergere il complesso verso il medesimo base...quindi.

Esempio:

#include <stdio.h>

long factorial (long);

main()
{
      int i;
      
      for(i = 1; i < 5; i++);
      
      printf("%2d! = %1d\n", i, factorial(i));
      
      return 0;
      }
 
      long factorial (long number){
           
           if(number <= 1)
           
           return 1;
           
           else
           
           return (number * factorial(number - 1));
      
      }

Allora, entriamo col numero 5 direttamente nella definizione di funzione, intesa come chiamata ricorsiva, il primo passo è l'if o else, in cui controllerà se ci sia il caso che conosce già, parte concettuale nota, altrimenti se il numero è superiore si entrerà nella chiamata ricorsiva, parte concettuale non nota.
bene ora il problema è qui che non mi è tanto chiaro...nel senso, io credo che funzioni cosi:
return (5 * factorial (5 - 1));
a sto punto creerà una nuova copia del problema, ma leggermente piu piccolo ovvero:
return (5 * factorial (4)); e poi
return(20 * factorial(3);
fino ad ottenere 1, e quindi 120?? è corretto il senso logico della questione??

7 Risposte

  • Re: Dubbio su ricorsione

    Si è corretto. Vuol dire che li hai capiti bene
  • Re: Dubbio su ricorsione

    In effetti non sono molto convenienti le ricorsioni...però non riuscivo a chiarire essendo abituato a chiamate di funzioni ben definite, e nell'ordine sequenziale, sono arrivato a pensare che il passo ricorsivo richiamasse la definizione...ehehehe va bene tutto ok..
  • Re: Dubbio su ricorsione

    Scusa sky...ma per quanto riguarda fibonacci?? anche qua mi sfugge sta cosa nel senso...
    
    long fibonacci (long n) /*Funzione ricorsiva*/
    {
    
    if(n == 0 || n == 1)
    
    return n;
    
    else
    
          return fibonacci(n - 1) + fibonacci(n - 2);
    }
    
    
    stando al ragionamento di poco fa, se inserisco ad esempio il 2...otterrò che

    return fibonacci(2 - 1) + fibonacci(2 - 2)
    return fibonacci(1) + (0) cioè = 1??
    ma col 5, non ritorna fibonacci(5)=5...come mai?
  • Re: Dubbio su ricorsione

    Il fibonacci della 5 iterazione = 0 1 1 2 3 5 = 5. A me viene quello.
    f(5) chiama f(4) + f(3)
    f(4) chiama f(3) + f(2)
    f(3) chiama f(2) + 1
    f(2) chiama 1 + 0

    tornando a ritroso trovi:
    f(5) chiama 3 + 2
    f(4) chiama 2 + 1
    f(3) chiama 1 + 1
    f(2) chiama 1 + 0

    f(5) = 5
  • Re: Dubbio su ricorsione

    E sul 6? f(6)=?
  • Re: Dubbio su ricorsione

    F(6) = F(5) + f(4) = (3+2) + (2+1) = 5 + 3 = 8
  • Re: Dubbio su ricorsione

    Ecco una funzione pseudo-ricorsiva che calcola le prime 92 iterazioni di fibonacci. Al 93 va in overflow perche non può rappresentare il numero
    
    #include <iostream>
    #include <map>
    using namespace std;
    
    
    std::map<__int64 ,__int64> F;
    
    __int64 fibonacci (__int64 n) /*Funzione ricorsiva*/
    {
    	std::map<__int64,__int64>::const_iterator it = F.find(n);
    	if(it != F.end())
    		return it->second;
    	else
    	{
    		__int64 i = fibonacci(n-1);
    		it = F.find(n-1);
    		if(it == F.end())
    			F[n-1] = i;
    		__int64 j = fibonacci(n-2);
    		it = F.find(n-2);
    		if(it == F.end())
    			F[n-2] = j;
    		return i + j;
    	}
    }
    
    int main(void)
    {
    	F[0] = 0;
    	F[1] = 1;
    	for(int i = 0; i < 93; i++)
    		cout << "F[" << i << "] = " << fibonacci(i) << endl;
       system("pause");
    }
    
    l'esecuzione è velocissima perche appena trovo una iterazione questa viene messa in una mappa e lo calcolo solo se non c'è nella mappa.
Devi accedere o registrarti per scrivere nel forum
7 risposte