[Generico] chiarimento su funzione ricorsiva

[anonimizzato]

Ciao a tutti,

avrei bisogno di un chiarimento, passo passo, per capire l'esatto funzionamento di una funzione ricorsiva.

Premesso che l'algoritmo e l'utilità mi è chiara, non riesco a focalizzare come venga costruito il risultato finale di tale funzione.

Mi spiego: prendiamo la classica serie di Fibonacci, risolta qui sotto con una funzione ricorsiva in Ruby.

def fattoriale(x)
risultato = 0
if (x == 0)
risultato = 1
else
risultato = x * fattoriale(x - 1)
end
risultato
end

puts fattoriale(4)

Quello che non riesco a stamparmi dentru u cevvelletto (Ras della fossa cit.) è come viene gestito ad ogni passaggio il valore nella variabile risultato dato che l'espressione

risultato = x * fattoriale(x - 1) non restituisce subito un valore a risultato (giusto?) ma richiama a sua volta la funzione.

Grazie in anticipo.

[anonimizzato]

Forse così: 4 x ( 3 x ( 2 x ( 1 x 1) ) ) ?


:help:

[WarDuck]

Il trucco è seguire passo passo le chiamate della funzione (prova ad eseguire la funzione "a mano" con carta e penna).

Supponendo che tu conosca bene il meccanismo delle chiamate a funzione (in generale), quello che devi notare è che ad ogni passo (se x > 0) viene chiamata la funzione con il parametro x decrementato di 1.

Questo significa che ad un certo punto dell'esecuzione arrivi al passo base, ovvero x = 0 (di fatto lì si interrompe la catena ricorsiva, perché la funzione ritorna 1).

[anonimizzato]

Questo significa che ad un certo punto dell'esecuzione arrivi al passo base, ovvero x = 0 (di fatto lì si interrompe la catena ricorsiva, perché la funzione ritorna 1).


Si si questo l'avevo capito.

Ho provato a mettere un puts davanti a

risultato = x * fattoriale(x - 1)

e se eseguo ad esempio fattoriale(4)

mi ritrovo in output:

1
2
6
24

non riesco però a capire come venga memorizzato il valore finale di risultato.

Ad ogni chiamata infatti viene re-inizializzato a 0 :eh:

[anonimizzato]

Supponendo che tu conosca bene il meccanismo delle chiamate a funzione (in generale)

In che senso?

[nuovoUtente86]

In che senso?

funzionamento dello stack

[anonimizzato]

funzionamento dello stack

Conosco stack, queue ecc. ma solo superficialmente. Non ho fatto l'UNI.

Ho trovato questo:
Una funzione ricorsiva "salva" il suo stato nel momento in cui richiama se' stessa, solitamente nello stack. Ogni volta che la ricorsione viene invocata, tutte le variabili presenti vengono inserite nello stack ed una nuova serie di variabili viene creata (sempre dallo stack).
http://www.soft-land.org/articoli/recurse

[tuccio`]

lo stack è una parte della memoria riservata alla memoria statica e alle chiamate a funzione, ogni volta che una funzione viene chiamata, viene allocata la memoria di cui necessita nello stack, e quando la chiamata finisce viene liberata (si chiama stack proprio perché funziona con politica lifo)

ad esempio, ogni volta che chiami la funzione fattoriale, viene allocata una nuova variabile risultato (quindi l'indirizzo su cui viene scritto il risultato per n sarà diverso dall'indirizzo su cui lo scrive per n-1)

tutto quello che devi pensare quando scrivi una funzione ricorsiva è:
posso risolvere un problema servendomi della soluzione a un problema "più piccolo" dello stesso tipo, in modo da potermi fermare prima o poi perché conosco la soluzione di un caso base? il funzionamento delle stack, l'albero delle chiamate ti possono aiutare a renderti conto che la cosa funziona

[anonimizzato]

lo stack è una parte della memoria riservata alla memoria statica e alle chiamate a funzione, ogni volta che una funzione viene chiamata, viene allocata la memoria di cui necessita nello stack, e quando la chiamata finisce viene liberata (si chiama stack proprio perché funziona con politica lifo)

ad esempio, ogni volta che chiami la funzione fattoriale, viene allocata una nuova variabile risultato (quindi l'indirizzo su cui viene scritto il risultato per n sarà diverso dall'indirizzo su cui lo scrive per n-1)

tutto quello che devi pensare quando scrivi una funzione ricorsiva è:
posso risolvere un problema servendomi della soluzione a un problema "più piccolo" dello stesso tipo, in modo da potermi fermare prima o poi perché conosco la soluzione di un caso base? il funzionamento delle stack, l'albero delle chiamate ti possono aiutare a renderti conto che la cosa funziona

Ok.

Mi potete confermare (o smentire) che, di fatto, il calcolo del risultato finale avviene partendo dalla chiamata più interna della ricorsione per, via via, tornare alla prima chiamata?

Cioè che in sostanza il calcolo avviene in una forma simile:

(1x2x3x4)

e non

(4x3x2x1)

come, magari, potrebbe sembrare inizialmente dato che il valore dell'argomento che passiamo alla funzione. quando chiamata nel nostro codice. è quello più alto (ad esempio 4) per:

fattoriale(4)

Grazie ancora.

[tuccio`]

se vuoi sapere se è così nella funzione che hai scritto, la risposta è sì

non puoi "linearizzare" così però

diciamo che è più come dire 4! = 4 * 3! e poi prendere un pezzo di carta su cui calcolare 3! = 3 * 2!, finché non arrivi a 0! fattoriale che sai essere 1

[anonimizzato]

se vuoi sapere se è così nella funzione che hai scritto, la risposta è sì

Perfetto, anzi per essere più preciso è forse così? :)

(((1x1)x2)x3)x4

[anonimizzato]

non puoi "linearizzare" così però

diciamo che è più come dire 4! = 4 * 3! e poi prendere un pezzo di carta su cui calcolare 3! = 3 * 2!, finché non arrivi a 0! fattoriale che sai essere 1

Ok, ora forse mi è più chiaro.

Anche scritta in questo modo infatti si intuisce la ricorsione.


4 * 3!
3! = 3 x 2!
2! = 2 x 1!

[nuovoUtente86]

Devi avere ben chiaro in mente come vengono allocati i record di attivazione delle varie chiamate a funzioni e le successive deallocazioni. Ha poco senso semplificare, come ti è stato detto, la cosa ad una visione lineare.

[anonimizzato]

Devi avere ben chiaro in mente come vengono allocati i record di attivazione delle varie chiamate a funzioni e le successive deallocazioni. Ha poco senso semplificare, come ti è stato detto, la cosa ad una visione lineare della cosa.

Comprendo.

Nel caso hai qualche riferimento online dove mi possa studiare meglio la cosa?

Grazie ancora.

[nuovoUtente86]

prendiamo la classica serie di Fibonacci
giusto per complettezza, la serie di Fibonacci (Fn= Fn-1 + Fn-2 ) e la funzione fattoriale non sono la stessa cosa.

[Albi89]

giusto per complettezza, la serie di Fibonacci (Fn= Fn-1 + Fn-2 ) e la funzione fattoriale non sono la stessa cosa.

Che poi a stretto rigore sarebbe una successione :fagiano:

[anonimizzato]

giusto per complettezza, la serie di Fibonacci (Fn= Fn-1 + Fn-2 ) e la funzione fattoriale non sono la stessa cosa.

Hai assolutamente ragione.

Ho usato l'esempio della serie di Fibonacci giusto come esempio per parlare delle funzioni ricorsive. ;)

[cionci]

Devi avere ben chiaro in mente come vengono allocati i record di attivazione delle varie chiamate a funzioni e le successive deallocazioni. Ha poco senso semplificare, come ti è stato detto, la cosa ad una visione lineare.
Secondo me no. A cosa gli serve il record di attivazione ?
Gli basta sapere ad ogni istante i valori delle variabili locali e dei parametri attuali.

Sgurbat: ribadisco, come ti era già stato consigliato, di seguire passo su passo su carta l'intera esecuzione con valori semplici
Prendendo l'esempio sopra, per scriverlo su carta scrivi il nome della funzione con i parametri attuali, seguita dalle operazioni eseguite e per ogni ricorsione indenta.

fattoriale(4):
risultato = 4 * fattoriale(3)
fattoriale(3):
risultato = 3 * fattoriale(2)
fattoriale(2):
risultato = 2 * fattoriale(1)
fattoriale(1):
risultato = 1 * fattoriale(0)
fattoriale(0):
risultato = 1
risultato = 1
risultato = 2
risultato = 6
risultato = 24


Puoi anche associare il funzionamento della ricorsione ad una dimostrazione per induzione.
Ad esempio:

Passo 0: - fattoriale(0) = 1
Passo 1: - fattoriale(1) = 1 * fattoriale(0)
Passo n: - fattoriale(n) = n * fattoriale(n-1)

In questo caso c'è un solo passo 0, che corrisponde ad una condizione di arresto. Nel caso ci fossero diverse condizioni di arresto, dovrai esplorare un passo 0 ed un passo 1 per ogni condizione di arresto. Il passo 1 corrisponde ad una chiamata della funzione che genera una ulteriore singola chiamata ricorsiva, la quale mette in atto la condizione di arresto da testare.
Questo modo di pensare ti tornerà molto utile anche per scrivere le funzioni ricorsive, non solo per capirle.

[nuovoUtente86]

Secondo me no. A cosa gli serve il record di attivazione ?
Gli basta sapere ad ogni istante i valori delle variabili locali e dei parametri attuali.

perchè dalla sua prima richiesta sembra che i dubbi non siano tanto sulla natura algoritmica del problema, quanto proprio sulla gestione delle chiamate. Probabilmente capire bene cosa avviene a basso livello, può fugare le incertezze. Ragionando ad un livello più astratto, probabilmente, nell' immediato e per funzioni semplici si ha una comprensione più veloce ma anche meno approfondita e stabile.

[cionci]

Secondo me ha poco senso conoscere il record di attivazione per comprendere come funzionano le chiamate ricorsive, anche perché il formato del record di attivazione non è standard e dipende dal compilatore e dalla macchina fisica/virtuale per cui si va a compilare/interpretare il linguaggio.
Giusto per fare un esempio comune: il formato del record di attivazione varia ad esempio fra IA32 e x86-64... Ad esempio in x86-64 non esiste un vero e proprio record di attivazione, ma per chiamate fino a, mi sembra, 8 parametri si fa uso dei registri general purpose per passare i parametri. Quindi anche semplicemente parlare di record di attivazione e stack in questo caso perde di significato.
Poi se si va a parlare di linguaggi interpretati/compilati JIT come nel caso sopra (è Ruby se non erro) le cose si fanno ancora più complicate...

[anonimizzato]

Ti ringrazio molto cionci, appena riesco mi studio bene i tuoi esempi. ;)

[nuovoUtente86]

Secondo me ha poco senso conoscere il record di attivazione per comprendere come funzionano le chiamate ricorsive, anche perché il formato del record di attivazione non è standard e dipende dal compilatore e dalla macchina fisica/virtuale per cui si va a compilare/interpretare il linguaggio.
Giusto per fare un esempio comune: il formato del record di attivazione varia ad esempio fra IA32 e x86-64... Ad esempio in x86-64 non esiste un vero e proprio record di attivazione, ma per chiamate fino a, mi sembra, 8 parametri si fa uso dei registri general purpose per passare i parametri. Quindi anche semplicemente parlare di record di attivazione e stack in questo caso perde di significato.
Poi se si va a parlare di linguaggi interpretati/compilati JIT come nel caso sopra (è Ruby se non erro) le cose si fanno ancora più complicate...

Nessuno ha mai detto di andare nello specifico del formato (non è questo che occorre), ma di capire, a linee generali come funzionano le cose a basso livello. Si tratta, semplicemente, di guardare la sequenza di esecuzione da un punto di vista meno astratto, avendo la consapevolezza di cosa avviene realmente (certo senza entrare nel dettaglio della singola architettura).

[Giovanni Tavella]

quando usi metodi con ricorsione è bene che nella firma li dichiari "statici".

Cioè


public static int fattoriale(int numero){

//caso base
if(numero==0 || numero==1) return 1;

else
return numero*fattoriale(numero-1);
//essendo un metodo "static" fattoriale ti restituisce un numero
}


quindi se il numero che gli passi è 3 fa cosi:

3 è uguale a 0 o 1?
no allora
3*fattoriale(3-1);//2

*
la seconda "kiamata" fà cosi:
2 è uguale a 0 o 1?
no,allora
2*fattoriale(2-1); //1
**
la terza "chiamata" fa cosi:
1 è uguale a 0 o 1?
si allora
ritorna 1

1*2*3


spero di esserti stato d'aiuto

[cionci]

Non mi sembra che si stia parlando di un linguaggio di programmazione in particolare...

[nuovoUtente86]

quando usi metodi con ricorsione è bene che nella firma li dichiari "statici".

Cioè


public static int fattoriale(int numero){

//caso base
if(numero==0 || numero==1) return 1;

else
return numero*fattoriale(numero-1);
//essendo un metodo "static" fattoriale ti restituisce un numero
}


quindi se il numero che gli passi è 3 fa cosi:

3 è uguale a 0 o 1?
no allora
3*fattoriale(3-1);//2

*
la seconda "kiamata" fà cosi:
2 è uguale a 0 o 1?
no,allora
2*fattoriale(2-1); //1
**
la terza "chiamata" fa cosi:
1 è uguale a 0 o 1?
si allora
ritorna 1

1*2*3


spero di esserti stato d'aiuto

I metodi statici non dipende dal tipo di implementazione (e non hanno nulla a che vedere con la ricorsione), ma sono tali in quanto il loro scope e il loro comportamento non sono relativi ad una singola istanza, ma ad una classe.

essendo un metodo "static" fattoriale ti restituisce un numero
e se non fosse stato dichiarato "static" che avrebbe restituito?

[Giovanni Tavella]

nuovoUtente86:
e se non fosse stato dichiarato "static" che avrebbe restituito?


hai ragione,mi sono espresso male, volevo dire che è un metodo che può essere invocato senza che occorra una istanza.

[tuccio`]

un'istanza di cosa? :asd:

[anonimizzato]

Ma cosa c'entra il discorso sul metodo "static" scusa? :mbe:

[dierre]

Poi se ti vuoi fare del male: http://en.wikipedia.org/wiki/Tail_recursion
E' una lettura interessante.