Rekurzió

Rekurzió olyan megközelítés, amelyben egy problémát úgy oldunk meg, hogy annak egy kisebb példányát ugyanolyan módon oldjuk meg, és az így kapott eredményt felhasználva jutunk el a végső megoldáshoz. A rekurzív definícióknak általában két része van: egy alap eset, amelyre közvetlen választ adhatunk, és egy rekurzív lépés, amely a problémát a kisebb méretű változatával operál.

Programozásban a rekurzív függvény saját magát hívja meg egy módosított bemenettel; a leállást az alap eset biztosítja. A verem (stack) a függvényhívások titkait őrzi; végtelen rekurzió vagy verem-túlcsordulás léphet fel, ha az alap eset hiányzik vagy a redukció nem ér el csökkenést.

Jellemző példák közé tartozik a faktoriális számítás, ahol n! = n·(n−1)!, alapérték a 0! = 1; a Fibonacci-sorozat, ahol f(n) = f(n−1) + f(n−2) alapértékekkel f(0) = 0, f(1) = 1; fa bejárások (mélységi bejárás); és rekurzív megvalósítású keresések vagy oszd meg és uralkodj típusú rendezések, mint a quicksort vagy a mergesort.

Változatai közé tartozik a kölcsönös rekurzió, a primitív és általános rekurzió matematikai fogalma, valamint a végső (tail) rekurzió, amelynél a hívásokat el lehet tüntetni a veremből egy fordító- vagy futtatókörnyezet optimalizációja révén. Gyakran alkalmazzák memoizációval vagy dinamikus programozással, hogy elkerüljék a felesleges számításokat.

Alkalmazási területek között szerepelnek algoritmusok, adatszerkezetek, nyelvtanok parsereinek felépítése és számos matematikai definíció formalizálása. A rekurzió kifejező ereje kényelmes, de teljesítménybeli megfontolásokat igényel.