Az előző megoldás az n-fokú lépcsőre vezető utak számát visszavezette az (n-1)-fokú, valamint az (n-2)-fokú lépcsőre vezető utak számára (azok összegére).
E deduktív megközelítéssel szemben induktív szemlélettel is hozzáláthatunk a megfelelő program megírásához: ha már tudjuk, hogy a lépcső aljától a k. lépcsőfokra elvezet egy út, akkor ebből levezethetünk egy-egy utat a (k+1)., továbbá a (k+2). lépcsőfokra: az előző úthoz értelemszerűen a következő, illetve az arra rákövetkező lépcsőfok sorszámát kell hozzáilleszteni.
A következő példákban nem tároljuk, csak kiírjuk a képernyőre lehetséges utakat; a kiírás mellett/helyett nyilván építhetnénk ezekből például egy listát.
A függvény hívásakor azt kérjük, hogy a 0. lépcsőfoktól a 6.-ig vezető utakat írja ki a program; a kiindulási lépéssort értelemszerűen az üres string határozza meg.
def ms_2311_012_01a(k, n, path):
if k<=n:
path+= str(k)
if k<n:
ms_2311_012_01a(k+1, n, path)
ms_2311_012_01a(k+2, n, path)
else:
print(path, end=' ')
ms_2311_012_01a(0, 6, '')
print()
A kimenet:
0123456 012346 012356 012456 01246 013456 01346 01356 023456 02346 02356 02456 0246
