A Fibonacci-sorozat

A Fibonacci-sorozat (A000045) a legismertebb rekurzív sorozatok egyike; ha máskor nem, ennek kapcsán érdemes lehet megismerkedni az egész számokból álló sorozatok címben is hivatkozott enciklopédiájával (oeis.org).

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

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)))

Első látásra meglepő, milyen lassan fut a program. Adott gépen, adott körülmények között a következő futásidőket jegyeztük föl n faktoriálisának, illetve az n. Fibonacci-számnak a kiszámítása után (értékek másodpercben, de ennek nyilván nincs jelentősége):

Önmagában a számított értékek nagyságrendje egyáltalán nem indokolja a mért értékek rohamos növekedését: az n. Fibonacci-szám nagyjából 1,6ⁿ körül van – ennél a faktoriálisok lényegesen gyorsabban nőnek.

A lassulás oka viszonylag könnyen megsejthető, illetve megérthető: az n. Fibonacci-szám kiszámításához két korábbi Fibonacci-számot határoz meg a program, és mivel a korábban kiszámolt számokat nem tároljuk, azokhoz két-két további számítást (azaz további négy függvényhívást) kell megvalósítani, és így tovább, (majdnem) mindig kétszerezve: a lépésszám n értékétől exponenciálisan függ – azért nem mondhatunk állandó kétszerezést, illetve az ennek megfelelő 2ⁿ-t, mert egyes ágakon hamarabb elérünk a kezdőtaghoz:

10┬8┬6┬4┬2
  │ │ │ └3┬1
  │ │ │   └2
  │ │ └5┬3┬1
  │ │   │ └2
  │ │   └4┬2
  │ │     └3┬1
  │ │       └2
  │ └7┬5┬3┬1
  │   │ │ └2
  │   │ └4┬2
  │   │   └3┬1
  │   │     └2
  │   └6┬4┬2
  │     │ └3┬1
  │     │   └2
  │     └5┬3┬1
  │       │ └2
  │       └4┬2
  │         └3┬1
  │           └2
  └9┬7┬5┬3┬1
    │ │ │ └2
    │ │ └4┬2
    │ │   └3┬1
    │ │     └2
    │ └6┬4┬2
    │   │ └3┬1
    │   │   └2
    │   └5┬3┬1
    │     │ └2
    │     └4┬2
    │       └3┬1
    │         └2
    └8┬6┬4┬2
      │ │ └3┬1
      │ │   └2
      │ └5┬3┬1
      │   │ └2
      │   └4┬2
      │     └3┬1
      │       └2
      └7┬5┬3┬1
        │ │ └2
        │ └4┬2
        │   └3┬1
        │     └2
        └6┬4┬2
          │  └3┬1
          │    └2
          └5┬3┬1
            │ └2
            └4┬2
              └3┬1
                └2

Ha valaki fogékony az effélére, örömmel fedezheti fel a fenti ábrában sok fraktálalakzat jellegzetes önhasonlóságát…