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:
n értéke | k értéke | lépésszám | futásidő |
10 | 5 | 503 | <10-3 |
20 | 10 | 369511 | 0,2 |
30 | 15 | 310235039 | 112 |
40 | 20 | ? | >86400 |
… | … | … | … |
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 2n helyett (a hasonló növekedési ütemet mutató) 1, 2, 5, 12, 27, 58, … sorozat tagjai adják meg (A000325).