Ricorsione

di
s.c.b.p.f.b.e
il
6 risposte
S
s.c.b.p.f.b.e
Utente Attivo
Iscritto da
dic, 2014
Messaggi:
76

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

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21595

    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);
}
  • Paolovox
    Paolovox
    Utente Attivo
    Iscritto da
    giu, 2014
    Messaggi:
    344

    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...
  • S
    s.c.b.p.f.b.e
    Utente Attivo
    Iscritto da
    dic, 2014
    Messaggi:
    76

    Re: Ricorsione

    Grazie mille ragazzi, credo di aver capito ora!
  • J
    JosAm93
    Pochi posts
    Iscritto da
    ott, 2016
    Messaggi:
    20

    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);
        }
}
  • CarDeFusco
    CarDeFusco
    Utente Attivo
    Iscritto da
    feb, 2016
    Messaggi:
    220

    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.
  • J
    JosAm93
    Pochi posts
    Iscritto da
    ott, 2016
    Messaggi:
    20

    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