Рекурсия

Знаеш ли какво е матрьошка? Първо виждаш само една фигура, обикновено дървена, която изглежда по подобен начин:

Можеш да махнеш горната половина на първата кукла и какво виждаш вътре? Друга, малко по-малка матрьошка!

Можеш да махнеш тази кула и да я разделиш на долна и горна половина. И ще видиш друга, още по-малка кукла:

И още веднъж:

И можеш да продължиш. Накрая ще намериш най-малката кукла. Тя има само една част и не се отваря:

Започнахме с една голяма матрьошка и видяхме все по-малки и по-малки кукли, докато стигнем до такава, която е толкова малка, че не може да съдържа друга кукла.

Какво е общото между матрьошките и алгоритмите? Точно както една кукла съдържа в себе си по-малка кукла, докато се стигне до мъничка кукла, която не може да съдържа в себе си друга, ще видим как да проектираме алгоритмите така, че да решават задачи, като решават по-малки инстанции на същата задача, докато стигнат до толкова малка задача, че можем да я решим директно. Наричаме тази техника рекурсия.

Рекурсията има много, много приложения. В този модул ще разберем как да използваме рекурсията, за да изчисляваме функцията факториел, да определяме дали една дума е палиндром, да изчисляваме степени на число, да рисуваме тип фрактали и да решаваме древната задача за Ханойските кули. Следващите раздели ще използват рекурсия, за да решават други задачи, включително сортиране.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.