Az előző szakaszban utaltunk már a Fibonacci-sorozat vegytisztán rekurzív számításának lassúságára. Megalapozottabb kijelentéseket tehetünk, ha megszámoljuk, hogy az n. tag kiszámításához hányszor hívtuk meg a rekurzív függvényünket, mellesleg kiíratva azt is, hogy éppen hányadik Fibonacci-szám értékét számítjuk (újra).
def fibonacci(n):
global stps
stps+= 1
if n==1 or n==2:
print('%d ' % (n))
return 1
else:
print('%d ' % (n), end='')
return fibonacci(n-2) + fibonacci(n-1)
stps= 0
print('Meghatározzuk a Fibonacci-sorozat n. tagját.')
n= int(input('Hányadik tag értékét számítsuk ki? '))
print('A(z) %d. Fibonacci-szám értéke %d' % (n, fibonacci(n)))
print('A függvényhívások száma %d volt.' % (stps))
Az n. tag kiszámításához szükséges függvényhívások számát a következő táblázatban foglaljuk össze:
| n értéke | lépésszám |
| 1 | 1 |
| 2 | 1 |
| 3 | 3 |
| 4 | 5 |
| 5 | 9 |
| … | … |
Kézenfekvő a szabály: az n. Fibonacci-szám kiszámításához eggyel több lépés kell, mint az előző kettőéhez összesen (az n.-hez meghívjuk a függvényt, majd az annyiszor hívja önmagát, mint ahányszor a megelőző két taghoz együttesen kellett).
A fenti (lépés)számokat nevezik néha Leonardo-számoknak is (A001595), a belőlük alkotott sorozat egymást követő tagjainak hányadosa –éppen úgy, mint a Fibonacci-sorozat esetén– (sqrt(5)+1)/2-höz tart. Ahogyan az oeis.org oldalon is olvasható, a két sorozatot további tulajdonságok is összekapcsolják. A lépésszámra vonatkozó összefüggés például úgy is megfogalmazható, hogy az n-edrendű Fibonacci-fa csomópontjainak számát éppen a megfelelő Leonardo-szám adja meg.
Végül hogy ebben az évben se maradjon ki, ezúttal is utalunk Edsger Wybe Dijkstra egy jegyzetére a Fibonacci-, illetve a Leonardo-számok kapcsolatáról: EWD-0797.
