Ricorsione

di il
6 risposte

Ricorsione

Buonasera ragazzi, ho un problema con la ricorsione, o meglio, non riesco proprio a capire il concetto di quest'ultima, se per esempio prendiamo questo codice:
#include <iostream>
using namespace std;


int factr(int n);


int main ()
{
    //uso della versione ricorsiva
    cout<< "4 fattoriale e' " << factr(4);
    cout << "\n";
    
    return 0;
}
//versione ricorsiva
int factr(int n){
    int answer;
    
    if(n==1) return (1);
    answer= factr(n-1)*n;
    return answer;
}

capisco che ogni volta che la funzione viene chiamata, associa ad 'answer' il valore di factr(n-1)*n, e quando l'argomento di factr diventa 1, la funzione ritorna il valore 1, ma poi non saprei come continua, qualcuno mi potrebbe dare una mano? grazie mille.

6 Risposte

  • Re: Ricorsione

    O anche, visualizzando la profondità di chiamate
    
    - chiama la fatt con n = 3
    	- salta la if dato che 3 > 1
    	- chiama la fatt con n = 2
    		- salta la if dato che 2 > 1
    		- chiama la fatt con n = 1
    			- esegue la if (infatti 1=1)
    			- restituisce il valore 1 al chiamante
    		- moltiplica 1 appena restituito per n = 1
    		- restituisce il risultato 1
    	- moltiplica 1 appena restituito per n = 2
    	- restituisce il risultato 2
    - moltiplica 2 appena restituito per n = 3
    - restituisce il risultato 6
    
    e puoi scrivere semplicemente una riga
    
    int fatt (int n)
    {
    	return(n<=1?1:fatt(n-1)*n);
    }
    
  • Re: Ricorsione

    Ti consiglio di studiare un pò gli algoritmi sugli alberi binari e magari passare ai grafi. Anche lo stack delle chiamate ricorsive e l'albero della ricorsione. Poi guarda il film Inception e Predestination che un pò rendono l'idea di ricorsione.
    Quando una funzione chiama se stessa avviene la ricorsione. Prima della chiamata, viene "congelato" lo stato attuale, così quando risali dalla catena della ricorsione, in quel punto ritroverai i dati che stavi elaborando in quel momento e magari con l'aggiunta dei dati che ti forniscono le chiamate "figlie".
    Un sacco di problemi in natura sono ricorsivi. Si nota anche nei frattali, come i broccoli ecc...
  • Re: Ricorsione

    Grazie mille ragazzi, credo di aver capito ora!
  • Re: Ricorsione

    Buonasera a tutti,
    a proposito di ricorsione, ho implementato un metodo per il calcolo del minimo comune multiplo tra 2 numeri, è corretto?
    
    int mcm(int a, int b)
    {
        int i=1;
    
        if (a%b == 0) return a;
        else if (b%a == 0) return b;
        else
        {
            i++;
            return mcm(a*i, b);
            }
    }
    
  • Re: Ricorsione

    JosAm93 ha scritto:


    Buonasera a tutti,
    a proposito di ricorsione, ho implementato un metodo per il calcolo del minimo comune multiplo tra 2 numeri, è corretto?
    
    int mcm(int a, int b)
    {
        int i=1;
    
        if (a%b == 0) return a;
        else if (b%a == 0) return b;
        else
        {
            i++;
            return mcm(a*i, b);
            }
    }
    
    Apri un nuovo post, non puoi chiederlo qui altrimenti non si capisce nulla.
  • Re: Ricorsione

    Scusatemi ho sbagliato allora, se necessario potete cancellare questo e il mio precedente post, ho aperto una nuova discussione nel forum C/C++.
Devi accedere o registrarti per scrivere nel forum
6 risposte