Comunque sia, la definizione della funzione di fibonacci, se non sbaglio, è proprio:
F0= 0; F1= 1; Fn = F(n-1) + F(n-2), con F0 aggiunto se si vuol far partire la successione con 0.
Dunque proprio la versione "ricorsiva" che si scrive.
http://it.wikipedia.org/wiki/Successione_di_Fibonacci