[Generico] chiarimento su funzione ricorsiva

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.

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

[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).

Originariamente inviato da WarDuck

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

Originariamente inviato da WarDuck

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

In che senso?

[nuovoUtente86]

Originariamente inviato da Sgurbat

In che senso?

funzionamento dello stack

Originariamente inviato da nuovoUtente86

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

Originariamente inviato da 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

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

Originariamente inviato da tuccio`

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

Originariamente inviato da tuccio`

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.

Originariamente inviato da 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 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]

Originariamente inviato da nuovoUtente86

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

Originariamente inviato da nuovoUtente86

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]

Originariamente inviato da 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.

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...