Инструменты пользователя

Инструменты сайта


rekursija

Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

rekursija [2012/06/21 05:02] (текущий)
Строка 1: Строка 1:
 +====== Рекурсия ======
 +**Рекурсия** – это прием программирования,​ при котором программа вызывает саму себя либо непосредственно,​ либо косвенно. Функция называется прямо рекурсивной,​ если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию,​ которая в свою очередь вызывает первую,​ то такая функция называется косвенно рекурсивной.
 +
 +Как правило,​ неопытный программист,​ узнав про рекурсию,​ испытывает легкое недоумение. Первая мысль – это бессмысленно!!! Такой ряд вызовов превратиться в вечный цикл, похожий на змею, которая съела сама себя, или приведет к ошибке на этапе выполнения,​ когда программа поглотит все ресурсы памяти. Однако рекурсия – это превосходный инструмент,​ который при умелом и правильном использовании поможет программисту решить множество сложных задач.
 +====== Определение рекурсивной функции ======
 +Функция называется рекурсивной,​ если во время ее обработки возникает ее повторный вызов, либо непосредственно,​ либо косвенно,​ путем цепочки вызовов других функций.
 +
 +Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.
 +
 +<​file>​
 +int a()
 +{.....a().....}
 +</​file>​
 +
 +Косвенной рекурсией является рекурсия,​ осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции,​ входящие в цепочку,​ тоже считаются рекурсивными.
 +
 +Например:​
 +
 +<​file>​
 +a(){.....b().....}
 +b(){.....c().....}
 +c(){.....a().....}
 +</​file>​
 +Все функции a,b,c являются рекурсивными,​ так как при вызове одной из них, осуществляется вызов других и самой себя.
 +====== Рекурсии или итерации?​ ======
 +С точки зрения теории,​ любой алгоритм,​ который можно реализовать рекурсивно,​ совершенно спокойно реализуется итеративно.
 +
 +Рекурсия производит вычисления гораздо медленнее,​ чем итерация. Кроме того, рекурсия потребляет намного больше оперативной памяти в момент своей работы. ​
 +
 +Значит ли это, что рекурсия бесполезна?​ Ни в коем случае!!! Существует ряд задач, для которых рекурсивное решение тонко и красиво,​ а итеративное – сложно,​ громоздко и неестественно.
 +
 +**Когда применять рекурсию?​**
 +  * для решения задач, для которых свойственна следующая черта: решение задачи сводится к решению таких же задач, но меньшей размерности и, следовательно,​ гораздо легче разрешаемых. ​
  
rekursija.txt · Последние изменения: 2012/06/21 05:02 (внешнее изменение)