Ну и где эта рекурсия

Рекурсия

Чтобы понять рекурсию, нужно сначала понять рекурсию.

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

Цикл

Удивительно, но в Haskell нет встроенных циклических конструкций, столь привычных для других языков. Ни тебе for , ни тебе while . Однако обойтись без циклов в нашем коде мы не сможем. Как же нам их организовывать?

К счастью, чаще всего нам это и не нужно. Вспомним нашу знакомую, функцию map :

map toUpper someList

Ну и чем же не цикл? На том же C это выглядело бы как-то так:

int length = . for(int i = 0; i < length; ++i) < char result = toUpper(someList[i]); . >

Функции наподобие map в подавляющем большинстве случаев избавляют нас от написания явных циклических конструкций, и это не может не радовать. Однако изредка нам всё-так придётся писать циклы явно. В Haskell, из-за отсутствия for -конструкции, сделать это можно только одним способом — через рекурсию (англ. recursion).

Идея рекурсии предельно проста:

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

Взглянем на определение функции map :

map _ [] = [] map f (x:xs) = f x : map f xs

А теперь разберём это интереснейшее определение по косточкам.

Правда о списке

Первым аргументом, как мы помним, выступает некая функция, а вторым — список, к элементам которого применяется эта функция. Но что это за странного вида конструкция в круглых скобках?

Это — особый образец, используемый для работы со списками. И чтобы он стал понятен, я должен рассказать вам правду о формировании списка.

Как мы помним, формируется список предельно просто:

[1, 2, 3] -- Список из трёх целых чисел.

Однако в действительности он формируется несколько иначе. Привычная нам конструкция в квадратных скобках есть ни что иное, как синтаксический сахар (англ. syntactic sugar). Синтаксическим сахаром называют некое упрощение кода, делающее его слаще, приятнее для нас. Если же мы уберём сахар (или, как ещё говорят, рассахарим код), то увидим вот что:

1 : 2 : 3 : []

Именно так список из трёх целых чисел формируется на самом деле. Стандартный оператор : нам уже знаком, мы встретились с ним в главе о списках:

newHost : hosts этот оператор берёт это значение и добавляет его в начало этого списка

То есть список строится путём добавления элемента в его «голову», начиная с пустого списка:

 1 : 2 : 3 : [] = 1 : 2 : [3] = 1 : [2, 3] = [1, 2, 3]

Начиная с правого края, мы сначала применяем оператор : к 3 и пустому списку, в результате чего получаем список с единственным элементом [3] . Затем, применяя второй оператор : к 2 и к только что полученному списку [3] , мы получаем новый список [2, 3] . И в конце, вновь применив оператор : к 1 и к списку [2, 3] , мы получаем итоговый список [1, 2, 3] . Вот почему столь удобно оперировать «головой» и «хвостом» списка. И именно поэтому был создан особый образец для паттерн-матчинговой работы со списком:

(head : tail)

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

main :: IO () main = print first where (first:others) = ["He", "Li", "Be"] _____ ____ ====== ==========

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

Но вы спросите, зачем нам это нужно? Если уж мы так хотим работать со списком через паттерн матчинг, можно ведь воспользоваться явным образцом:

main :: IO () main = print first where [first, second, third] = ["He", "Li", "Be"] _____ ____ ====== ==== +++++ ++++

Всё верно, однако образец с круглыми скобками чрезвычайно удобен именно для рекурсивной работы со списком, и вот почему. Вспомним определение функции map :

map f (x:xs) = f x : map f xs _ _ == ==

Подставим реальные значения на основе примера про перевод символов строки в верхний регистр:

map f (x:xs) = f x : map f xs map toUpper "neon" = toUpper 'n' : map toUpper "eon" _ _ === ===

Вот теперь-то мы видим, каким образом функция map пробегается по всему списку. Пройдёмся по итерациям, чтобы всё окончательно встало на свои места. У нас же цикл, верно? А где цикл — там итерации.

На первой из них оператор : применяется к выражениям toUpper ‘n’ и map toUpper «eon» . Выражение слева вычисляется и даёт нам символ ‘N’ :

toUpper 'n' : map toUpper "eon" 'N' : map toUpper "eon"

Выражение справа содержит применение той же функции map , то есть мы входим в цикл, во вторую его итерацию:

map toUpper "eon" = toUpper 'e' : map toUpper "on"

Выражение слева вычисляется и даёт нам ‘E’ :

toUpper 'e' : map toUpper "on" 'E' : map toUpper "on"

Вычисляем выражение справа — и входим в следующую итерацию:

map toUpper "on" = toUpper 'o' : map toUpper "n"

Выражение слева даёт нам ‘O’ :

toUpper 'o' : map toUpper "n" 'O' : map toUpper "n"

Справа вновь применение map — и наша последняя итерация:

map toUpper "n" = toUpper 'n' : map toUpper []

Выражение слева даёт нам ‘N’ :

toUpper 'n' : map toUpper [] 'N' : map toUpper []

Мы вытащили из списка последний из четырёх символов, и список остался пустым. Что же мы будем делать дальше? А дальше мы вспоминаем первый вариант определения функции map :

map _ [] = []

Здесь функция говорит: «Как только я вторым аргументом получу пустой список, я, игнорируя первый аргумент, немедленно дам тот же самый пустой список». Поэтому оставшееся на последней итерации выражение справа:

map toUpper []

подойдёт под данный случай и просто даст нам пустой список. Всё, готово, работа функции завершена. На каждой итерации мы откусываем «голову» списка и передаём её функции toUpper , «хвост» же передаём вновь функции map . На четвёртой итерации упираемся в пустой список и возвращаем его же. Совместив все итерации воедино, получаем вот что:

'N' : 'E' : 'O' : 'N' : []

Узнаёте? Это же наш рассахаренный список, соединяющийся воедино:

['N', 'E', 'O', 'N']

Вот мы и пришли к нашему равенству:

 map toUpper "neon" = map toUpper ['n', 'e', 'o', 'n'] = ['N', 'E', 'O', 'N'] = "NEON"

Туда и обратно

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

map _ [] = [] -- Выходим из цикла. map f (x:xs) = f x : map f xs -- Зацикливаемся, -- применяя саму себя.

Если бы мы опустили первое определение, компилятор предусмотрительно сообщил бы нам о проблеме:

Pattern match(es) are non-exhaustive

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

Для любопытных

Открою секрет: рекурсивными в Haskell бывают не только функции, но и типы. Но об этом в последующих главах.

Дню Сурка посвящается… Рекурсия в реальной жизни

Февраль. Ну, привет, февраль. Мы тебе рады. А сегодня — и подавно. Потому что 2 февраля — самый цикличный и рекурсивный день в мире благодаря фильму «День Сурка».

В этом цикле зимы можно-таки ещё разок посмотреть тот самый «День Сурка» (2.02) и «День Радио» (13.02), поболеть за любимых спортсменов на Зимней Олимпиаде (9.02-25.02), поесть блинов (12.02-16.02), подарить «Валентинку» (14.02) и очередной лосьон для бритья (23.02), поздравить с праздником полярного медведя (27.02)… А там и новый цикл весны наступит.

А теперь о сегодняшнем. Главный герой фильма «День Сурка» попал в некую рекурсивную ситуацию, которая похожа на бесконечный цикл. На деле в каждый из дней происходит ряд событий, в которые герой так или иначе может вмешаться. Герой резонно предположил, что для выхода из дня сурка он должен что-то сделать с этими ситуациями. Сложность в том, что ситуаций много, способов вмешательства в них — тоже, а уж комбинаций того и другого — и того больше. Делать нечего, он стал досконально изучать свой единственный повторяющийся день, полагая, что выходом из него может стать что угодно — от кражи сурка до самоубийства. Постепенно он пришёл к мысли о самосовершенствовании. Чтобы обнаружить точку выхода, герой должен использовать знания, полученные в предыдущие проживания этого дня, и постепенно ему это удалось. Но рекурсию можно встретить не только в программировании или фантастических фильмах. Это вполне распространенное явление даже в повседневной жизни. Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.

Рекурсия — не обязательно бесконечна. Вот, например, матрёшка. Вполне рекурсивна, но вы обязательно доберётесь до самой маленькой из них.

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

Примеры рекурсии в природе

Самым зрелищным примером рекурсии являются географические объекты. Например, похожие на вышеупомянутые матрешки, острова посреди озер, которые в свою очередь расположены на островах. Среди таких объектов самым известным является пресноводное озеро Тааль, расположенное на острове Лоусон в провинции Батангас, Филиппины. На озере находится вулканический остров Тааль, в его кратере имеется еще одно озеро. А на нем в свою очередь есть свой собственный небольшой остров, Вулкан-Пойнт.

Наглядным примером также являются реки, образованные из других рек, горы и молнии.

Не менее интересны примеры «овощных» рекурсий. Вот, к примеру, обычный репчатый лук и белокочанная капуста:

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

Дерево состоит из веток. Ветка в свою очередь состоит из более маленьких веточек. Каждая ветка повторяет дерево.

Такую же структуру можно наблюдать у сложного листа папоротника:

Семена некоторых цветов (например, подсолнечника) расположены пересекающимися спиралевидными веерами, определяемыми соотношением чисел Фибоначчи:

Замечательным примером рекурсии являются дендриты — сложнокристаллические образования древовидной ветвящейся структуры. Нам всем знакомы ледяные дендриты — это снежинки и морозные рисунки на стекле:

Также встречаются дендриты металлов, например, золота и меди:

Примеры рекурсии из животного мира, тоже достаточно наглядны: извечная пара «курица и яйцо» и … эволюция:

Примеры рекурсии в лингвистике и литературе

Рассказ из «Кибериады» Станислава Лема о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей. (бесконечная рекурсия — каждая новая машина строила себе подобную). Н.В. Гоголь в повести «Портрет» описывает сон художника Черткова, который проснувшись снова попадает в сон, проснувшись от этого сна он опадает в первый сон, от которого тоже придется проснуться. «Мастер и Маргарита» — один из наиболее ярких рекурсивных романов. Тема Иешуа и Пилата рекурсивно вызывается из темы Мастера и Маргариты. Кроме того, здесь так же используется прием «книга в книге». Мастер пишет роман об Иешуа и Пилате, текст которого сливается с текстом книги «Мастер и Маргарита». Еще один пример рекурсии «Дом, который построил Джек» Роберта Бернса в переводе Маршака. Или вот, самый короткий рассказ Айзека Азимова, написанный на спор прямо в студии во время записи интервью.

«…Вставьте шплинт А в гнездо Б…»

Дейв Вудбери и Джон Хэнсен, неуклюжие в своих скафандрах, с волнением наблюдали, как огромная клеть медленно отделяется от транспортного корабля и входит в шлюз для перехода в другую атмосферу. Почти год провели они на космической станции А-5, и им, понятное дело, осточертели грохочущие фильтрационные установки, протекающие резервуары с гидропоникой,генераторы воздуха, которые надсадно гудели, а иногда и просто выходили из строя.

— Все разваливается, — скорбно вздыхал Вудбери, -потому что все это мы сами же и собирали.

— Следуя инструкциям, — добавлял Хэнсен, — составленным каким-то идиотом.

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

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

Этот-то робот и находился сейчас в разгружающейся клети. Вудбери нервно задрожал, когда створки шлюза наконец сомкнулись за ней.

Самыми же известными примерами бесконечной рекурсии в литературе являются «бесконечные сказки»: Я открыл свои глаза: Голубые небеса, И зелено покрывало, И мохнатые леса… Вот и речка — все течет, Солнце встало — вновь печет… Взял я ручку и тетрадь И решил все записать, Я открыл свои глаза: Голубые небеса… У попа была собака У попа была собака, Он ее любил, Она съела кусок мяса, Он ее убил И в землю закопал, И памятник поставил, И надпись написал: У попа была собака, Он ее любил, Она съела кусок мяса

Примеры рекурсивной графики

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

Рекурсивный юмор

Это просто жесть. Программисты, епта, живем втроем, договорились так: первый будит второго, второй третьего, третий первого… рекурсия =) в результате проспали лекцию. У нас на обед — салат «Рекурсивный» : помидоры, огурцы, салат. xxx: помнишь Антоха желание проиграл? так вот, я ему загадал: чтобы он 2 дня на все предметы, с которыми совершил какие-либо действия клеил стикер с этим действием yyy: я бы точно клеил бы на стикер стикер с надписью «наклеил». Мелкого (сына 10 мес) вогнал в рекурсию… одна соска во рту. дал вторую. первую от радости выплюнул. вставил вторую. услышал как что-то упало. обрадовался увидев первую соску. выронил вторую. засунул первую в рот. услышал как что-то упало… уже 5 минут меняет их. Сегодня работал с отцом, он мне говорит типа «хочешь рекурсию покажу?», я типа «ну давай». Он берет втыкает вилку дрели в удлинитель, а вилку удлинителя втыкает в свободную розетку этого же удлинителя, жмет кнопку, дрель начинает работать… Блин наверное у меня было очень смешное лицо, он ржал до вечера, а я еще долго втыкал почему же так получается. Оказалось дрель была на аккумуляторе. Если же вы считаете, что все в жизни должно иметь прикладное применение, то предлагаем вам вспомнить полученные знания по программированию и попробовать решить некоторые из известных задач, которые решаются с помощью рекурсивных методов: нахождение чисел Фибоначчи и факториала, а также головоломку «Ханойские башни».

Рекурсия. Беглый взгляд

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

Примечание: Данная небольшая статья написана для беглого ознакомления с рекурсией, некоторыми примерами её применения и опасностями.

Определение

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

Самая большая глупость — это делать то же самое и надеяться на другой результат.

Под рекурсией понимают процесс повторения элементов самоподобным образом. Объект обладает рекурсией, если он является частью самого себя.

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

Некоторые примеры

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

Отличный пример вы можете найти тут.

Самое известное программисту применение рекурсии — задачи на вычисление чисел Фибоначчи или факториала. Давайте покажем, как это реализовать на языке C:

int fib(int n)

Можно показать, как это выглядело бы на Prolog

fib(1,1):-!. fib(2,1):-!. fib(N,R):- N1 is N-1, fib(N1, R1), N2 is N-2, fib(N2, R2), R is R1 + R2.

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

Вычисление факториала. Пример хвостовой рекурсии

int factorial_rec(int n, int res) < if (n == 0) return res; return factorial_rec(n - 1, res * n); >int factorial(int n)

Ещё один опасный и интересный пример

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

 #include int main()

Reboot кнопкой после такого делать немного не приятно.

Для математика первой ассоциацией, скорее всего, будет фрактал. Фракталы прекрасны и приятно для глаза показывают свойства самоподобия.

Самые известные фракталы:

Кривая (снежинка) Коха
Треугольник Серпинского

Дерево Пифагора

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

Углубимся глубже

Проста ли рекурсия? Однозначно нет. На вид кажется, что всё просто, однако рекурсия таит в себе опасности (А иногда она просто не понятна).

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

Заметим, что дерево вызовов получится большим, но максимальное количество вызовов в стеке будет заметно меньше (N-1 при N > 2, соответственно).

Пример дерева вызовов для числа 6

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

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

Для полноты картины обязательно надо упомянуть о борьбе с рекурсией.

Зачем же с ней бороться?

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

Под силу ли побороть любую рекурсию?

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

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

Заключение

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

UPD: Добавлен корректный пример хвостовой рекурсии.

Научный форум dxdy

Здравствуйте.
Очень хочу разобраться с рекурсией. Я понимаю что э то такое (вызов функцией/процедурой самой себя), но как этим пользоваться еще не разобрался. Если кто знает какие-нибудь простенькие задачки на эту тему, пожалуйста дайте ссылку.
Язык желательно Basic или C++
Заранее огромное спасибо

24.01.2009, 08:27

Ну, классический пример на рекурсию — это вычисление факториала(возможно, Вы его уже видели).

То есть, чтобы вычислить факториал, нужно вычислить предыдущий факториал, и домножить его на . Тут главное вовремя остановиться А именно, в рекурсивной функции должна быть нерекурсивная ветка, иначе все зациклится.
На C это выглядит так:

int factorial(int n)
{
if (n == 0)
return 1; //нерекурсивная ветка
else
return n*factorial(n-1); //рекурсия
}

Еще рекурсия часто применяется в алгоритмах типа «разделяй и властвуй». Почитайте, например, про Quicksort: http://ru.wikipedia.org/wiki/ Быстрая_сортировка

24.01.2009, 08:34

C сортировкой я разобрался.
но вот решение задачки о ханойской башне, например, для меня уже тяжеловато. Я совсем запутался =(

24.01.2009, 11:18
KiberMath писал(а):

C сортировкой я разобрался.
но вот решение задачки о ханойской башне, например, для меня уже тяжеловато. Я совсем запутался =(

С ханойской башней непонятен алгоритм, или как писать программу?
24.01.2009, 14:41

Никак не могу разобраться с самим алгоритмом. Какие действия должна делать та функция которая вызвает сама себя.
. вообще интересно даже не то какие действия должна делать эта функция а как разобраться с тем какие действия должна делать эта функция. Интересен сам ход рассуждений.
С переводом алгоритма на язык программирования проблем никаких нет.

24.01.2009, 23:47
Привет. Вырезал из книжки Либерти для расчета ряда Фибоначчи, может поможет:

int fib(int n);
int main()
{
int n,answer;
std::cin >> n;

answer = fib(n);
.
return 0;
}
int fib (int n)
{
if (n < 3)
return (1);
else
return( fib(n-2) + fib(n-1) );
}

Извини, что не аккуратно, просто времени мало.

25.01.2009, 00:38

Зачем вообще разбираться с рекурсией?
Это очень вредное явление . т.е. способ мышления.
Я в своё время ,после того как с ней разобрался . очень долго отвыкал, в смысле — отвыкал думать рекурсивно — это было трудно, почти как бросить курить . наверное.

25.01.2009, 00:47
Андрей АK
Почему вредное?
25.01.2009, 01:20
KiberMath , видел на википедии код решения ханойской башни рекурсией? Что там не ясно?
Здесь
25.01.2009, 02:18

apatic
Так не интересно ))
Я сам хочу придумать алгоритм, а потом сравню

Добавлено спустя 5 минут 29 секунд:

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

Добавлено спустя 11 минут 27 секунд:

Андрей АK
И почему если рекрсия вредна так много олимпиадных задач связанных с рекурсий.

25.01.2009, 02:34

KiberMath , я просто не понял, что тебе нужно? Я думал проблема в том, что ты не понимаешь рекурсии, потом думал, что ты не понимаешь конкретный алгоритм, а теперь узнается, что ты не знаешь алгоритм, а сам его хочешь сочинить. =) В чем нужна помощь? Попробуй до конца понять, что есть рекурсия, посмотри алгоритм, который я для тебя отсканил.
«Рекурсия используется, когда можно выделить самоподобие задачи.» © wiki

25.01.2009, 14:51
Хм.
А как решить эту задачу без использования рекурсии.
25.01.2009, 19:58
KiberMath в сообщении #181029 писал(а):
Хм.
А как решить эту задачу без использования рекурсии.
25.01.2009, 20:06
KiberMath писал(а):
Андрей АK
Почему вредное?

Во первых, рекурсивные алгоритмы не приспособлены для оптимизации рессурсов.
Мало того что сами они рессурсоёмкие (на каждый вызов процедуры система тратит кучу памяти и скорости), но они не позволяют производить никаких улучшений.
С ростом сложности задачи всё большее количество памяти требуется передавать через стэк — т.е. с увеличением сложности время выполнения возрастает в некой прогрессии.
Кроме того — эту рессурсоёмкость очень трудно оценить — невозможно с первого взгляда догадаться, сколько системе потребуется памяти для такой-то задачи.
Во вторых,
Конечно , зачастую рекурсивный алгоритм выглядит красиво и компактно . но это может сыграть злую шутку с мозгами и стилем программирования.
Как только вы привыкаете что-то делать при помощи рекурсии, это начинает входить в привычку — даже те задачи, где можно было бы без неё обойтись, вы начинаете решать с помощю рекурсии.
Но если вдруг в вашу логику где-то вкралась ошибка — её иногда трудно обнаружить изучая код рекурсивной программы.
Отладка рекурсивных функций также усложнена.
Рекурсия — она проста и крассива только на небольших и несложных примерах, с увеличением же объёма и сложности она становиться громоздкой и неуклюжей.
А отвыкать уже тяжело — мозги привыкли думать рекурсивно, под конец (когда болезнь совсем запущена) вы уже пытаетесь любой цикл в своей программе заменить рекурсией (циклы уже мозгом не воспринимаются как удачное решение).

Однако, любую рекурсивную программу всегда можно заменить циклом.
Да, приходится использовать массивы считать сколько надо выделить памяти под них . но ведь чтоб программа хорошо работала всё равно всё это придётся делать.
К тому-же циклы хорошо оптимизируются (в т.ч. рапараллеливаются) , легче отлаживиются, алгоритм предстаёт более явно и наглядно — сразу видны все слабые места и пути оптимизации.

Короче — если хотите писать хорошие программы — никогда не используйте рекурсию.

25.01.2009, 20:39
Йа Гринько писал(а):
KiberMath в сообщении #181029 писал(а):
Хм.
А как решить эту задачу без использования рекурсии.

Мда. не уточнил извеняюсь. Я Ханойскую башню имел в виду

Добавлено спустя 1 минуту 27 секунд:

Андрей АK Огромное спасибо за объяснение!
apatic Пасиб большое за скан и за ссылку

Страница 1 из 2

[ Сообщений: 28 ]

На страницу 1 , 2 След.

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей