Ciao a tutti. Mi chiamo Diego e sono un ragazzo di 26 anni. Non ho trovato una sezione del forum dedicata alle presentazioni quindi ho pensato di farlo qua

Ho iniziato con la programmazione da niente (letteralmente qualche ora) e ho qualche problema di comprensione per quanto riguarda la successione Fibonacci

def Fibonacci (n): 
  if n == 0 or n == 1: 
    return 1 
  else: 
    return Fibonacci(n-1) + Fibonacci(n-2)

Ora, la prima parte è abbastanza chiara, ma dopo else tutto diventa confuso. Se io scrivessi Fibonacci(6) il programma mi restituirebbe in maniera corretta 13. Ciò che non capisco è come il programma arrivi a questa cifra seguendo le indicazioni fornite.




- Se n è uguale a 0 o a 1, ritorna 1.
- Altrimenti ritorna: Fibonacci(6-1) + Fibonacci(6-2)



Seguendo alla lettera quanto scritto il risultato dovrebbe essere 9 (sbagliando), invece che 13. Ovviamente sto interpretando male io, solo non capisco come. Qualcuno potrebbe aiutarmi?

Il poco intuitivo non sta tanto nella successione, ma nel fatto che è ricavata usando la ricorsione invece di un procedimento lineare.

Fibonacci(6-1) vale 8
Fibonacci(6-2) vale 5
e 8+5=13, quindi è corretto dire che Fibonacci(6) vale 13.

A sua volta Fibonacci(5) vale 8 perché
Fibonacci(4) vale 5 e
Fibonacci(3) vale 3
5+3=8

E Fibonacci(4) vale 5 perché
Fibonacci(3) vale 3 e
Fibonacci(2) vale 2
3+2=5

Quella non è una semplice funzione, ma una funzione che chiama innumerevoli copie distinte di sè stessa passando ogni volta valori sempre più piccoli. Vogliamo vedere quante funzioni vengono tirate in ballo da un semplice Fib(6)?

count = 0

def Fibonacci (n): 
  global count
  count += 1
  if n == 0 or n == 1: 
    return 1 
  else: 
    return Fibonacci(n-1) + Fibonacci(n-2)


Fibonacci(6)
print(count)

Il valore di count alla fine è 25, questo vuol dire che per calcolare un semplice Fib(6) vengono avviate 25 diverse funzioni Fibonacci, ciascuna che ritorna un valore parziale, il cui totale alla fine viene sommato da quella principale e ritornato come risultato.

Diciamo che la ricorsione è da sempre un argomento avanzato, difficile da seguire mentalmente, e poco usata perché può produre un'esplosione esponenziale di chiamate e occupazione di memoria... con Fibonacci(10) vengono chiamate 177 funzioni, con Fibonacci(20) diventano 21891, con Fibonacci(30) siamo a 2692537

...ma viene mostrata come esempio didattico per la soluzione di problemi che hanno una descrizione intrinsecamente ricorsiva (fibonacci, fattoriale ecc)

Ciao Claudio, grazie mille per la risposta. Il concetto come lo spieghi mi è chiaro.
Solo ancora non capisco come faccia Python a ricavare il giusto procedimento da quelle 5 righe di programma

Ti dispiacerebbe indicarmi il processo del programma nel ricavare il risultato corretto (quando avrai tempo e voglia, si intende)? Un po' come quello fatto da me nel primo post, però corretto.