Рекурсия: что это такое?

Категория: Что такое?

– Автор: Игорь (Администратор)

Хоть термин рекурсия чаще всего используют в сфере ИТ, всё же это слово не является большой редкостью и в обычной жизни. Неужели никто никогда не слышал такую фразу как "Это рекурсия какая-то!" (обычно с нотками удивления и негодования)? Конечно, же слышали.

Собственно, о том, что значит рекурсия, и о некоторых нюансах, и пойдет речь в данном обзоре.

Рекурсия это

Рекурсия - это ситуация, когда объект (описание, определение, изображение и т.д.) или процесс определяется в терминах самого себя, или типа объекта или процесса. Простыми словами рекурсия это когда нечто состоит из себе подобного. Данный термин используется во многих сферах, но наиболее часто в математике и информационных технологиях.

Рассмотрим простой пример для понимания. Матрёшки. Внутри большой матрёшки находится матрёшка поменьше (но такого же вида), внутри которой находится матрёшка ещё меньшего размера, внутри которой находится ещё меньшая матрёшка. И так далее.

Рекурсия в жизни

Самый банальный и знакомый многим пример рекурсии в жизни - это получение справок. Допустим, вам нужна справка А. Какой ваш алгоритм действий? Очень простой. Посмотрели список нужных документов, взяли с собой и пришли получать. Но, когда вы пришли, "вдруг" оказывается, что нужна ещё справка Б (ну или справка была в списке документов). Какие ваши дальнейшие шаги? В общем-то, точно такие же. Потом окажется, что для справки Б нужна справка В и так далее.

Что происходит, по сути? Каждый раз, когда вы топаете за следующей справкой, вы приостанавливаете текущий алгоритм действий. Соответственно, когда вы получаете недостающую справку, вы возвращаетесь к получению приостановленной справки. Скажем, получили справку В. Что дальше делаете? Как не сложно догадаться, топаете получать справку Б. Потом топаете получать справку А.

Вообще, рекурсия в жизни это не такое уж и редкое явление. Например, как растут ветки деревьев. Из основного ствола вырастают одни ветки. Потом эти ветки разрастаются и из них начинают расти ещё ветки. И так далее.

Рекурсия в программировании

Немалая часть задач в программировании решается с помощью рекурсии потому, что это гораздо проще, чем выстраивать сложные циклические алгоритмы. Чтобы лучше понять, рассмотрим пример для понимания.

Абстрактная задача, которую, в принципе, можно решить простым циклом, но это чтобы не усложнять пример. Допустим, вам нужно вычислить факториал n!. Вот как это будет выглядеть на php:

function fact($n) {
    if ($n == 0) return 1;
    return $n * fact($n - 1);
}

Не сложно заметить, что код достаточно простой и понятный. И логика его следующая. В принципе, n! = n * (n-1)!. Иными словами, чтобы найти факториал числа n, нужно просто умножить текущее число n на факториал числа меньшего на 1, которое вычисляется по аналогичной логике.

Примечание: Нужно правильно понять первичное утверждение. Любую рекурсивную задачу можно решить через циклы и дополнительные переменные (стеки с данными и т.д.), но это может сделать алгоритм более сложным для понимания и поиска ошибок.

Достоинства и недостатки рекурсии

Достоинства рекурсии:

1. Рекурсивный подход всегда проще для понимания. Первое время рекурсивные алгоритмы кажутся сложными и непонятными, но после того, как вы начинаете понимать их суть, создавать и читать такие алгоритмы становится существенно проще, чем циклические (естественно, в случае соответствующей задачи).

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

Недостатки рекурсии:

1. Рекурсию нужно понимать. Например, если в рекурсивном алгоритме не добавить условие выхода (или в неправильном месте указать), то такой алгоритм может выполняться бесконечно.

2. Циклические алгоритмы обычно быстрее и менее требовательные, чем рекурсивные. В данном случае речь чисто о технических моментах в программировании. Если коротко, то экономия достигается за счёт уменьшения издержек (не нужно запускать копию алгоритма и полностью сохранять все локальные переменные и состояние алгоритма).

3. Рекурсию нужно уметь применять тогда, когда она нужна. Привычка решать все рекурсивные задачи без циклов легко может привести к тому, что либо программа станет крайне сложной для понимания и поиска ошибок (особенно, если одни рекурсивные алгоритмы будут запускать другие и так далее), либо будет не особо эффективной.

Примечание: Стоит знать, что существуют языки, которые либо являются рекурсивными, либо подразумевают частое использование рекурсии (например, prolog). Однако у них свои особенности и они не так распространены, как, например, php, С++, Java и прочие.

Так же вам может быть интересен обзор Уникальное или универсальное решение: что лучше?

Понравилась заметка? Тогда время подписываться в социальных сетях и делать репосты!