Чем рекурсия отличается от цикла

Чем рекурсия отличается от цикла

Здесь легко и интересно общаться. Присоединяйся!

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

цикл — фиксированное количество шагов на которых выполняется действие, рекурсия выполняется до тех пор пока не сработает условие выхода из рекурсии — а их два по большому счету: 1) закончились данные, 2) найдено нужное значение. а так они похожи внешне

У каждого способа решения задачи свои преимущества, но…
Любую рекурсивную функцию можно заменить циклом и стеком.

Лепота спасет людей Назначение человека: 1) постигнуть смертельную опасность, источником которой оказался он сам, человек; 2) постигнуть, что нельзя спастись, не возвысившись духовно; 3) свершить духовный подвиг спасения – самоспасения и спасения жизни как таковой; 4) благоговеть перед живой жизнью, лелеять, совершенствовать и расселять ее в Галактике Млечного Пути; 5) оживить, очеловечить, одухотворить сам Космос; 6) утверждать бытие – против небытия и под угрозой небытия; 7) открывать и открывать заново – с болью и счастьем, что «сострадание есть главнейший и, может быть, единственный закон бытия всего человечества»

видимо его отсутствием.

— алгоритмы, последовательно приближающиеся к заданной цели;

— алгоритмы, в которых поиск решения сводится к формулировке одной или нескольких задач меньшей размерности;

— алгоритмы, соблюдающие установленные для них соотношения (свойства, «законы», инварианты);

Соответственно, меняется и технология их разработки: основной задачей является – направить алгоритм «в нужное русло», заставить двигаться его в нужном направлении, соблюсти «правила игры», правильно свести задачу к аналогичной. Очевидность и наблюдаемость здесь уступают место логической непротиворечивости и доказательности соблюдения программой заданных свойств.

7 .1. Цикл, итерация, рекурсия

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

Рекурсия в жизни, литературе, искусстве

Примеры рекурсии можно встретить в литературе, искусстве, фольклоре.

«У попа была собака, он ее любил.

Она съела кусок мяса, он ее убил.

Камнем придавил, и на камне написал:

Я хочу Вам написать, что я хочу Вам написать, что я хочу Вам написать . . .

«Я оглянулся посмотреть,

не оглянулась ли она,

чтоб посмотреть, не оглянулся ли я. »

В тамбуре, пуская дым в окошко, Монахов на некоторое время обрел пространство: мусорный ящик, огнетушитель, декларация какая-то под стеклом, дверь в туалет, плевок – все на месте. Давно пора было закурить… подчеркнуто выпустил дым – отлегло. Что это все на него находит? Благожелательно приласкал взглядом огнетушитель: на месте, друг! Не действуешь. И то, что на огнетушителе была картинка, на которой человек, успев переодеться в комбинезон, правильно держал в руках точно такой же огнетушитель, на котором, в свою очередь, была картинка, на которой… это, с детства запавшее представление, тут же тысячу раз проигранное в мозгу, не было почему-то ему противно, наоборот: усмехнулся себе ласково, будто подмигнул прошлому… (Андрей Битов. “Вкус”).

Читайте также:  Как вернуть переписку в телеграмме

Все образные примеры рекурсии подмечают главное ее свойство: некоторая часть системы воспроизводит самое себя. Здесь же отмечается особенность такого подхода: рекурсия не свойственна обыденному восприятию, безусловная рекурсия бесконечна и бессмысленна. Ограниченная рекурсия с определенным количеством уровней – парадоксальна и опасна. Например, рефлексия (от лат. reflexio – обращение назад) – самопознание, самонаблюдение, образное представление самого себя в третьем лице (см., например, «Поединок» А.Куприна).

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

В программировании таких примеров еще больше :

— определение любого конкретного оператора (условный, цикл, блок) в качестве составных частей включает произвольный оператор;

— рекурсивная структура данных — элемент структуры данных содержит один или несколько указателей на аналогичную структуру данных. Например, односвязный список можно определить как элемент списка, содержащий указатель NULL или указатель на аналогичный список;

— рекурсивная функция — тело функции содержит прямой или косвенный (через другую функцию) собственный вызов.

Рекурсивные алгоритмы и функции и их свойства

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

//—— Циклический алгоритм вычисления факториала

for (int s=1; n!=0; n—) s *=n;

//—— Рекурсивный алгоритм вычисления факториала

return n * fact(n-1); >

Приведенный пример не демонстрирует каких-то особенных преимуществ линейной рекурсии. Тем не менее, линейная рекурсия элегантно смотрится на линейных структурах данных – односвязных списках.

//— Включение в односвязный с сохранением порядка – циклическая программа

// pr — указатель на предыдущий элемент списка

void InsSort(list *&ph, int v)

// перед переходом к следующему указатель на текущий

// запоминается как указатель на предыдущий

for ( p=ph,pr=NULL; p!=NULL && v>p->val; pr=p,p=p->next);

if ( pr == NULL ) // включение перед первым

else // иначе после предыдущего

< q ->next = p ; // следующий для нового = текущий

pr -> next = q ; >> // следующий для предыдущего = новый

//— Рекурсивное включение в односвязный список с сохранением порядка

void InsSort(list *&ph, int v)<

list * pp = new list ; // меньше следующего

ph == pp ; // ради присваивания по ссылке — рекурсия

else InsSort ( ph -> next , v ); // иначе – рекурсивный вызов для следующего

Особенность включения в односвязный список – указатель на новый элемент должен быть помещен в предыдущий элемент списка, указатель на который программа должна «помнить». Рекурсия позволяет использовать ссылку на указатель для любого элемента списка.

Читайте также:  Смартфон asus zenfone max zc550kl black

… if () F 1(); // Не более 2 рекурсивных вызовов

for ( int i =0; i m ; I ++) F 2(); // Рекурсивный вызов в цикле

Все приведенные выше литературно-художественные примеры имеют отношение к линейной рекурсии. Для ветвящейся рекурсии есть только одна физическая аналогия – цепная реакция: каждый рекурсивный вызов порождает n себе подобных. В структурах данных аналогичная «конструкция» называется деревом.

void main() void F() void F() void F()

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

— в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров. Обычно это производится в порядке, обратном их следованию в списке;

— при вызове функции в стек записывается точка возврата — адрес той части программы, где находится вызов функции;

— в начале тела функции в стеке резервируется место для локальных (автоматических) переменных.

Перечисленные переменные образуют группу (фрейм стека). Стек «помнит историю» рекурсивных вызовов в виде последовательности (цепочки) таких фреймов. Программа в каждый конкретный момент работает с последним вызовом и с последним фреймом. При завершении рекурсии программа возвращается к предыдущей версии рекурсивной функции и к предыдущему фрейму в стеке.

Рекуррентные соотношения

Рекуррентные соотношения определяют некоторый элемент последовательности через несколько предыдущих. Например, числа Фибоначчи: F ( n )= F ( n -1)+ F ( n -2), где F (0)=1, F (1)=1. Если рассматривать этот ряд от младших членов к старшим, способ его построения задается итерационным циклическим алгоритмом.

// Вычисление чисел Фибоначчи итерационным методом

// F 2 – «позавчерашнее» значение ряда

// F 1 – «вчерашнее» значение ряда

// F 0 – «сегодняшнее» значение ряда

F 2= F 1, F 1= F 0; // при переходе к следующему шагу текущий становится

В данной последовательности нет необходимости использовать массив, поскольку вычисляемые элементы последовательности находятся рядом, иначе потребуется более «глубокое» запоминание. Это же соотношение, вычисляемое наоборот, последующий – через предыдущие, напрямую реализуется рекурсивной функцией.

// Рекурсивное вычисление чисел Фибоначчи

if ( n >=1) return 1; // Для первых двух членов ряда — 1

return F ( n -1)+ F ( n -2); // Результат – сумма рекурсивно вычисленных значений

Трудоемкость рекурсивных алгоритмов

Трудоемкость – это зависимость времени выполнения алгоритма от размерности входных данных. В рекурсивных функциях размерность входных данных определяет глубину рекурсии. Если имеется ветвящаяся рекурсия – цикл из m повторений, то при глубине рекурсии N общее количество рекурсивных вызовов будет порядка N m , поскольку с каждым шагом рекурсии оно увеличивается в m раз. Показательный характер функции говорит о том, что трудоемкость рекурсивных алгоритмов значительно превышает трудоемкость известных нам алгоритмов сортировки и поиска. Для различных случаев рекурсивных алгоритмов, когда задача размерности n сводится к задаче меньшей размерности (обычно n /2 или n -1) и при этом содержит определенное количество операций, кратное текущей размерности 1 или n , результирующие значения трудоемкости несложно оценить.

Читайте также:  Форум покупок в интернет магазинах

Изменение размерности задачи

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

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

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

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

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

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

С точки зрения теории вычислительных процессов программа с рекурсией может быть заменена эквивалентной программой с циклами.

Какая альтернатива предпочтительна в программировании?

Что проще писать, читать, поддерживать?

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

  • Вопрос задан более трёх лет назад
  • 17362 просмотра

Все зависит от задачки. Порою достаточно простого цикла, с ним и работать проще и нет проблем со стеком. Еще, лучше все таки в цикле решать задачи, где результат следующего полностью зависит от результата предыдущего (например, факториал).

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

Еще рекурсия будет эффективна, если рекурсивная функция кешируемая, например, она запоминает результат и при следующем запросе просто возвращается кешированный вариант.

Ссылка на основную публикацию
Часы с функцией диктофона
Классические часы с секундной стрелкой; Цифровые часы (поддержка 12/24ч форматов, для смены формата сделайте двойной тап по цифрам); Диктофон (поддержка...
Формула vlookup на русском
Функция ВПР в Excel позволяет данные из одной таблицы переставить в соответствующие ячейки второй. Ее английское наименование – VLOOKUP. Очень...
Формула в эксель вычитаем проценты
В различных видах деятельности необходимо умение считать проценты. Понимать, как они «получаются». Торговые надбавки, НДС, скидки, доходность вкладов, ценных бумаг...
Часы с которых можно звонить детские
Ребенка, который самостоятельно посещает школу или гуляет с друзьями, подстерегает много опасностей. Решить эту проблему помогут технологичные детские умные часы...
Adblock detector