La ricorsione: efficienza (2)

• L'implementazione ricorsiva vista in precedenza non è efficiente.

• Si può dimostrare che se S è il tempo necessario al calcolo del numero di fibonacci di indice N (fN), il calcolo di fN+1 richiede circa 1,6xS.

• Ad esempio se il calcolo di fN richiede 1 s, il calcolo di fN+18 richiederà un'ora.

Note: