Рекурсия - это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной.

Плюс рекурсии – простота алгоритма, а так же лаконичность кода. Для примера рассмотрим алгоритм выхода из лабиринта, заданного прямоугольной матрицей, где 1 – стена, 0 – свободное место, 2 – выход.
Алгоритм простейший:

Но у такого алгоритма есть один существенный минус – он требует огромных машинных ресурсов. Посудите сами, необходимо хранить в памяти для каждой "копии" функции все те данные, которыми вы пользовались, не говоря уже о самой функции. Конечно, на современных машинах при решении простых задач это не столь критично, но всё же следует осторожно относиться к рекурсивным алгоритмам.

Существует теорема, в которой говорится о том что любая рекурсия может быть заменена на линейный алгоритм. К сожалению, я не могу привести ссылку.
Рассмотрим преобразование рекурсивного алгоритма в линейный на примере поиска по вложенным директориям.
Алгоритм прост: читаем директорию, если находим новую директорию, вызываем скрипт заново:

А теперь рассмотрим как можно преобразовать данный алгоритм в линейный. Обратимся к сути алгоритма: нам нужно по очереди читать  записи из текущей директории и искать в под директориях новые папки.
Значит можно очередную найденную папку просто добавить в некий список, очередь, вместо того чтобы вызывать для него процедуру:

Отдельное спасибо участнику dimes за ошибку найденную в коде примеров.
P.S. В этой статье я хотел показать, что собой представляют рекурсивные алгоритмы и как их можно заменить линейными.