Recursivitatea

Ai văzut vreodată un set de păpuși rusești? Mai întâi, vezi doar o figurină de lemn pictată, care seamănă cu cea de mai jos:

Poți desface jumătatea de sus a primei păpuși. Ce găsești înăuntru? Altă păpușă rusească, puțin mai mică!

Poți scoate acea păpușă și o vei desface și pe ea. Astfel, vei găsi o altă păpușă și mai mică:

Și încă una:

Și continui tot așa. În cele din urmă, vei găsi cea mai mică păpușă rusească. Aceasta este dintr-o singură bucată, deci ea nu mai poate fi desfăcută:

Am început cu o păpușă mare rusească, apoi am văzut păpuși rusești din ce în ce mai mici, până când am ajuns la cea mai mică și care nu mai conține nimic.

Ce legătură au păpușile rusești cu algoritmii? La fel cum păpușile rusești conțin, pe rând păpuși din ce în ce mai mici, până când se ajunge la una prea mică pentru a mai conține ceva, vom proiecta și noi algoritmi pentru rezolvarea unei probleme prin trecerea la alte probleme asemănătoare dar mai mici, până când se ajunge la o problemă atât de mică încât poate fi rezolvată direct. Această tehnică se numește recursivitate.

Recursivitatea are foarte multe aplicații. În acest modul vom vedea cum se folosește recursivitatea pentru a calcula funcția factorial, pentru a determina dacă un număr este sau nu palindrom, pentru a calcula puterile unui număr, pentru a desena anumiți fractali, pentru a rezolva problema turnurilor din Hanoi. În modulele următoare, vom folosi recursivitatea pentru a rezolva alte probleme, inclusiv sortarea.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.