Ricorsione - Python, domanda con valore di ritorno

Question

Mi rendo conto che potrebbe sembrare una domanda sciocca, ma l'ultima volta che l'ho programmato era in assembler, quindi il mio pensiero potrebbe essere spento:

Una funzione ricorsiva in questo modo:

def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n - 1)

Perché quando la funzione raggiunge n == 0 non restituisce 1 ma piuttosto la risposta che è fattoriale. Sto pensando a qualcosa come nell'assemblatore sarebbe quando n == 0:

mov eax, 1
ret

Perché il codice sopra funziona, suppongo che python restituisca l'ultimo valore nello stack prima di quella condizione?

Answer 1

Pensa in questo modo, ad esempio per fac (5) :

return 5 * fac(4)
           return 4 * fac(3)
                      return 3 * fac(2)
                                 return 2 * fac(1)
                                            return 1 * fac(0)
                                                       1

Quindi 1 sarà il primo valore restituito ma verrà restituito a fac (1) e fac (1) verrà restituito a fac (2) e così via.

Answer 2

restituisce 1 quando n == 0. Quel valore di ritorno viene estratto dallo stack dal sito chiamante, che era l'invocazione in n * fac (n - 1) . Quel 1 viene moltiplicato per n e restituito, ecc.

Answer 3

Se chiami fac (0) restituirà 1 (non 0, ma suppongo che sia solo un refuso nella tua domanda). Se chiami fac (1), andrà nella clausola else e lì chiamerà fac (0) . Questo restituirà 1. Quindi calcolerà n * 1, che è 1, e lo restituirà. Se chiami fac (2) andrà anche nella clausola else, dove chiamerà fac (1) che come menzionato sopra restituirà 1, quindi n * fac (n-1) sarà 2 e questo è il valore di ritorno di fac (2) . E così via. Spero che sia spiegato per te.

Answer 4

Non viene restituito in modo implicito nulla: quando n = 0, la funzione immette l'istruzione if e restituisce 1 direttamente dall'istruzione return 1 . Tuttavia, questo non è il punto in cui la risposta "quotata" è fattoriale viene restituito all'utente. Al contrario, potrebbe restituire questo valore a chiamata funzione invocata da fac (1), che nel mezzo del ramo n * fac (n - 1) . Quindi ci vorrà il "1" restituito e restituito n * 1 , ovvero da 1 a è chiamante. Se questo è fac (2), restituirà n * 1 o 2 in è chiamante e così via.

Così fac (5) viene tradotto come:

fac(5) = 5 * fac(4) = 5 * (4 * fac(3) = 5 * (4* (3 * fac(2)) = 5 * (4* (3 * (2 * fac(1)) = 5 * (4* (3 * (2 * (1 * fac(0)) = 5*4*3*2*1*1

Solo dopo che il valore 1 viene restituito attraverso ogni livello superiore, ritorna al primo chiamante e la moltiplicazione in ogni fase fornisce la risposta.

Answer 5

James, quando la chiamata finale alla tua funzione (quando n == 0) ritorna è solo una delle diverse istanze di fac (n) nello stack di chiamate. Se dici print (fac (4)), lo stack è essenzialmente:

fac(0)
fac(1)
fac(2)
fac(3)
fac(4)
print()

L'ultima chiamata a fac (0) restituisce appropriatamente 1, tuttavia in Python hai richiesto il valore di ritorno della prima chiamata a fac (n), fac (4).

Non pensarlo come un ciclo in cui scoppierà 'ret', il ritorno conclude semplicemente una delle diverse esecuzioni in sospeso.