Rekurzió

Láttál már Matrjoska babát? Először csak egy babát látsz, általában festett fából van, ami valahogy így néz ki:

Ha leveszed az első baba tetejét, mit találsz? Egy másik, valamivel kisebb babát!

Kiveheted ezt a babát is, szétszedheted a tetejét és az alját, és mit találsz? Egy még kisebb babát!

És újra:

És tovább folytathatod. Végül találni fogsz egy ici-pici babát, ami már nem szedhető szét:

Egy nagy babával kezdtük, egyre kisebb és kisebb babákat találtunk, amíg el nem jutottunk egy olyan pici babához, ami már olyan kicsi volt, hogy abba már nem fért volna el egy másik baba.

Mi a közös a Matrjoskában és az algoritmusban? Látni fogjuk, hogy hasonlóan ahhoz, ahogy az egyik babában benne rejlik egy másik, kisebb baba, míg el nem jutsz a legapróbb babáig, ami már olyan kicsi, hogy abba már nem fér el még egy baba, analóg módon elkészíthetünk egy algoritmust egy adott probléma megoldására úgy, hogy az adott probléma egyre kisebb változatát vesszük, mindaddig, amíg a problémát le nem szűkítettük annyira, hogy azt már közvetlenül meg tudjuk oldani. Ezt a technikát hívjuk rekurziónak.

A rekurziónak rengeteg alkalmazása van. Ebben a modulban meg fogjuk vizsgálni, hogyan alkalmazhatjuk a rekurziót a faktoriális függvény kiszámításához, annak eldöntésére, hogy egy adott szó oda-vissza értelmes-e, számok hatványának kiszámítására, egyfajta fraktál kép rajzolásához, és az ősi hanoi torony feladvány megoldásához. A későbbiekben pedig további problémákat oldunk meg rekurzióval, többek közt a rendezést.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.