De ce contează?
Ai văzut vreodată păpușile rusești matrioșka? Deschizi una și înăuntru e alta mai mică, apoi alta și mai mică — până dai de una micuță care nu se mai deschide. O funcție recursivă lucrează exact așa: ca să rezolve o problemă, o deschide într-una mai mică de același fel, apoi în alta și mai mică… până ajunge la una atât de simplă încât răspunsul e imediat. Aceea e păpușica ce nu se mai deschide.
Intuiția
O funcție este recursivă când se autoapelează pe o subproblemă mai mică decât cea
primită. Nu e un truc de sintaxă: e o cale de a descrie o problemă prin ea însăși.
În clasa a 7-a ai întâlnit factorial. Acum privește mecanismul cu ochiul de clasa a
10-a: dacă știi deja răspunsul pentru cazul mai mic, îl combini cu pasul curent și ai
răspunsul mare. Două ingrediente sunt obligatorii — fără ele recursia fie nu se oprește,
fie nu pleacă nicăieri.
Orice funcție recursivă are exact două părți:
- Cazul de bază — o problemă atât de mică încât răspunsul e direct (oprește coborârea).
- Pasul recursiv — exprimă problema printr-una mai mică și se apropie de cazul de bază.
Lipsește baza → recursie infinită. Pasul nu micșorează → nu ajungi niciodată la bază.