RicPol said @ 2018-11-20 21:48:16:

Non ci sono molte soluzioni per capire la ricorsione: bisogna mettersi lì con carta e penna e fare il conto, e poi rifarlo e rifarlo ancora finché non capisci come funziona. Per prima cosa, riscriviamo la funzione formattandola con l'apposito pulsante "code" (quello con il simbolo "<>") in modo che si capisca di che cosa parliamo:

def binario(n):
    if n==0:
        return ''
     

Ora, è chiaro che se ti metti con carta e penna a calcolare "binario(353646545521)" non ne esci vivo. Però carta e penna è l'unico modo, fidati. Proviamo insieme a calcolare cosa succede quando scrivi

binario(5)  # dà "101", ovviamente

Allora, sei pronto? Via:


PRIMO PASSAGGIO: "binario(5)"
- 5 è uguale a 0? No, andiamo avanti
- 5%2 è uguale a 1. Quindi la stringa finale terminerà per "1"
- 5//2 è uguale a 2. Quindi dobbiamo calcolare binario(2)
- stato attuale: la stringa è "....1", e dobbiamo calcolare binario(2)

SECONDO PASSAGGIO: "binario(2)"
- 2 è uguale a 0? No, andiamo avanti
- 2%2 è uguale a 0. Quindi aggiungiamo a sinistra uno "0" alla stringa finale
- 2//2 è uguale a 1. Quindi dobbiamo calcolare binario(1)
- stato attuale: la stringa è "...01", e dobbiamo calcolare binario(1)

TERZO PASSAGGIO: "binario(1)"
- 1 è uguale a 0? No, andiamo avanti
- 1%2 è uguale a 1. Quindi aggiungiamo a sinistra un "1" alla stringa finale
- 1//2 è uguale a 0. Quindi dobbiamo calcolare binario(0)
- stato attuale: la stringa è "...101", e dobbiamo calcolare binario(0)

QUARTO PASSAGGIO: "binario(0)"
- 0 è uguale a 0? Sì, quindi aggiungiamo una stringa vuota ("") a sinistra alla stringa finale, e usciamo
- stato attuale: la stringa è "101", e non dobbiamo calcolare più nessuna ricorsione.

Risultato: "101"

Se non sei riuscito a seguire questi passaggi, ripetili con carta e penna finché non ci riesci. Se ci sei riuscito, prova almeno altre cinque volte con carta e penna a fare altri calcoli semplici (binario(3), binario(7), binario(9)...) finché non hai interiorizzato come funziona. Purtroppo la ricorsione funziona così, devi trovare il modo di immaginarti nella testa lo stack delle chiamate successive e i risultati parziali.




--- Ultima modifica di RicPol in data 2018-11-20 21:49:07 ---

RicPol said @ 2018-11-21 10:18:55:

Eh, diciamo che non hai capito la cosa fondamentale. Mettiamola così: a ogni iterazione, quella funzione restituisce un "coso" nella forma:

R + S

dove "S" è una stringa, e "R" è il risultato di un'altra ricorsione. Quindi, dopo un po' di volte che ripeti la ricorsione, hai un "coso" di questo tipo:

(((((...) + S) + S) + S) + S)

dove "..." rappresenta il livello di ricorsione che hai raggiunto attualmente. Arrivati all'ultima ricorsione, la funzione restituisce una stringa vuota e si ferma (cioè non chiama più se stessa). Quindi, dopo l'ultima ricorsione, tu avrai un "coso" finale di questo tipo:

(((((("") + S) + S) + S) + S) + S)

che è ovviamente la somma di varie stringhe, ossia una stringa. In altre parole, la stringa finale è il risultato dell'accumulo progressivo delle "stringhe-resto" prodotte a ogni successiva ricorsione, più l'ultima stringa vuota di chiusura. (Le "stringhe-resto", come spero avrai capito, sono i resti convertiti in stringa: questo algoritmo mappa la procedura che faresti con carta e penna per convertire un intero decimale in binario).





Esercizio numero 1: che cosa garantisce che a un certo punto la funzione "esca", e non continui a ricorrere all'infinito? Ovvero, che cosa garantisce che si arrivi sempre, a un certo punto, allo zero e quindi a chiamare "binario(0)"?

Esercizio numero 2: che cosa succede se, arrivati a zero, la funzione non esce restituendo la stringa vuota, ma qualsiasi altra cosa? Cioè, per esempio, se scrivo:

def binario(n):
    if n==0:
        return None # o "return 42", o "return False", qualunque cosa
    etc etc etc come sopra

La funzione "funziona" ancora? E perché?

Esercizio numero 3: scritta in questo modo la funzione ha un piccolo baco: se chiami "binario(0)" il risultato è una stringa vuota, cosa ovviamente sbagliata. Il binario di 0 invece è "0", ovviamente. Il problema è che quando la funzione testa "if n==0" non riesce a distinguere se sta parlando proprio del numero originale oppure del numero che riceve a una ricorsione successiva. Cioè non riesce a distinguere se in quel momento sta eseguendo la prima ricorsione, o è già arrivata a una ricorsione successiva. Bisognerebbe correggere la funzione con qualcosa del genere:

# pseudo-codice
def binario(n):
    if n==0 and siamo-alla-prima-ricorsione:
        return "0"
    if n==0 and siamo-oltre-la-prima-ricorsione:
        return ""
    etc etc come sopra

C'è un modo per fare questo? (questo esercizio è un po' più difficile. Forse puoi usarlo per fare l'ingenuo e trollare il tuo prof. C'è una discreta possibilità che così su due piedi non lo sappia fare neanche lui).





Detto questo, il tuo problema resta lo stesso: posso guidarti per mano, centimetro dopo centimetro; posso farti un milione di esempi e di metafore; ma se non ci ragioni sopra con la tua testa, perderndoci una giornata (ma una giornata seria, intendo: col telefonino spento, senza distrazioni, senza musica... come si faceva una volta) non ci riuscirai mai. E' proprio qualcosa che ti scatta nella testa, e deve scattarti perché riesci a visualizzarlo alla tua maniera. Poi prova con gli esercizi che ti ho proposto, poi prova altre funzioni ricorsive, eccetera.


La ricorsione non è difficile di per sé: tuttavia è oggettivamente difficile visualizzare il flusso del programma ricorsivo nella testa. C'è solo da mettersi lì con pazienza e carta e penna.