Az előző szakaszok után joggal vetődik fel a kérdés: mi értelme lehet ilyen lassú rekurzív függvényeket írni, ha sokkal gyorsabban is megkaphatjuk a kívánt számeredményeket?
Ahogyan korábban már utaltunk rá, a lassulás végső oka egy exponenciálisan szélesedő fa bejárása – ennek megfelelően például nincs jobb megoldás akkor, ha valamiért ténylegesen be kell járnunk a fát. Kézenfekvő módon lehet szükség erre, ha olyan eseteket kell felsorolnunk, amelyek egy efféle fa levelein vagy csomópontjain helyezhetőek el.
>Ilyen feladat szerepel például a Mozaik Kiadó 11.-es matematikatankönyvének 12. oldalán: hányféleképpen mehetünk fel –mondjuk– egy hatfokú lépcsőn, ha egyesével vagy kettesével szedjük a fokokat?
Ügyes diák megfelelő előkészítés után megtalálhatja, értelmes diák hamar megértheti a Fibonacci-számokról szóló választ – az összes eset módszeres felsorolása azonban egyáltalán nem tűnik könnyűnek.
>Lássunk elsőként egy olyan megoldást erre, amely egy listát épít a megtalált bejárási lehetőségekből. Az algoritmus lényegében csak a lehetséges esetek számáról szóló állítást, illetve annak bizonyítását formalizálja: egy lépcsőhöz egyetlen lehetséges út tartozik, két lépcsőhöz a megadott kettő; minden más esetben tekintsük az eggyel korábbi fokra vezető utak egy lépéssel megtoldott, továbbá a kettővel korábbi fokra vezető utak kettős lépéssel megtoldott meghosszabbítását.
def ms_2311_012_01(n):
if n==1:
return ['1']
elif n==2:
return ['11', '2']
else:
l1= ms_2311_012_01(n-1)
for i in range(len(l1)):
l1[i]+= '1'
l2= ms_2311_012_01(n-2)
for i in range(len(l2)):
l2[i]+= '2'
return l1+l2
print(ms_2311_012_01(6))
Az eredményül kapott lista:
['111111', '21111', '12111', '11211', '2211', '11121', '2121', '1221', '11112', '2112', '1212', '1122', '222']
