A binomiális együtthatók

Nem meglepő, hogy a binomiális együtthatók (rekurzív) számolása éppen úgy lassul, mint a Fibonacci-számoké: ebben az esetben is két korábbi érték (újbóli és újbóli) kiszámítása teszi exponenciálissá a megoldás időigényét.

def sub(n, k):
    global stps
    stps+= 1
    if k==0 or k==n:
        print('(%d %d)' % (n, k))
        return 1
    else:
        print('(%d %d)' % (n, k), end='')
        return sub(n-1, k-1) + sub(n-1, k)

stps= 0

print('Meghatározzuk az n alatt k binomiális együttható értékét.')
n= int(input('Mennyi legyen a binomiális együtthatóban n értéke? '))
k= int(input('Mennyi legyen a binomiális együtthatóban k értéke? '))
print('%d alatt %d értéke %d' % (n, k, sub(n, k)))
print('A függvényhívások száma %d volt.' % (stps))

Néhány binomiális együttható kiszámításához a függvényhívások számát, illetve a futásidő (másodpercben mért) értékeit a következő táblázatban foglaljuk össze:

A lépésszámokat kézenfekvő módon a Pascal-háromszöghöz hasonló módon határozhatjuk meg: a széleken ezúttal is 1-esek állnak, de a köztes értékeket a fölöttük lévő két szám eggyel növelt összegeként kaphatjuk meg:

          1
        1   1
      1   3   1
    1   5   5   1
  1   7  11   7   1
1   9  19  19   9   1

Az egyes sorokban álló számok összegét most 2ⁿ helyett (a hasonló növekedési ütemet mutató) 1, 2, 5, 12, 27, 58, … sorozat tagjai adják meg (A000325).