Задачки на рекурсию.

[ИС]

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

[Maslov]

Чтобы почувствовать рекурсию во всей её красе, я бы порекомендовал поиграть в какой-нибудь из языков функционального программирования, типа Lisp или Scheme.
Рекурсия в императивных языках - это жалкое подобие того, что с ней вытворяют в функциональных, где никаких других способов организации итеративных процессов просто нет.
Scheme предпочтительнее, ибо проще, но Lisp, F# и даже Хаскель тоже вполне подойдут.
Есть неплохие книжки, например, П.Хендерсон. Функциональное программирование. Применение и реализация.
Может быть, вот такую книгу ещё будет полезно посмотреть:Баррон Д. Рекурсивные методы в программировании (Мир, 1974, 80 стр.)

[e2e4]

Цитата:

А то я пока очень плохо составляю алгоритмы использующие рекурсию (

И это здорово. Тем больше шансов составить нормальный, итерационный алгоритм .

Конечно, все зависит от ваших целей, но изучать рекурсию ради того, чтобы изучать рекурсию... увольте. Что конкретно вы от нее хотите? Ну порешайте классические задачки на поиск чисел Фибоначчи, факториала числа и Ханойские башни. От себя могу добавить задачку - "из монохроматической картинки выделить в отдельный массив все фигуры. Фигура состоит из всех точек, которые соседствуют друг с другом" - рекурсией решается очень просто.

А вообще-то, рекурсия хороша только для решения задач, для которых более быстрый алгоритм (с циклами) не придумывается. Все остальное - минусы.

[Бодигрим]

Самая первая задача на рекурсию - составить алгоритм для нахождения факториала заданного числа. Можете? Следующий шаг - рекурсивный алгоритм Евклида для нахождения НОД. Еще традиционно рекурсией решают задачу о ханойских башнях.

Еще здорово рисовать всякие фракталы - мы в свое время рисовали снежинки на Logo. Из более сложных примеров - это алгоритм быстрой сортировки.

[ИС]

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

[Maslov]

e2e4 в сообщении #255492 писал(а):

И это здорово. Тем больше шансов составить нормальный, итерационный алгоритм .

А почему Вы считаете итерационные алгоритмы более "нормальными", чем рекурсивные?

e2e4 в сообщении #255492 писал(а):

Конечно, все зависит от ваших целей, но изучать рекурсию ради того, чтобы изучать рекурсию... увольте.

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

e2e4 в сообщении #255492 писал(а):

А вообще-то, рекурсия хороша только для решения задач, для которых более быстрый алгоритм (с циклами) не придумывается. Все остальное - минусы.

Это слишком сильное утверждение. Любой рекурсивный алгоритм может быть сведен к итеративному (в конце концов, можно имитировать стек вызовов вручную).
Что касается "быстроты", то, во-первых, не факт, что итеративная процедура будет работать заметно быстрее, чем рекурсивная, а во-вторых, во многих случаях те 3% выигрыша в скорости работы программы, которые обеспечит итеративный алгоритм, сведутся на нет усложнением программы и увеличением времени разработки. Ещё раз хотелось бы подчеркнуть: речь идёт только о тех задачах, где рекурсия является естественной.
Факториал и функция Фибоначчи - на мой взгляд, не очень удачные примеры, т.к. они прекрасно решаются обычным циклом. А уж рекурсивная реализация вычисления функции Фибоначчи, по два раза считающая каждое значение - это, скорее, пример того, как не надо использовать рекурсию.

[ИСН]

(в сторону) Есть такая наука - отыскание наихудших алгоритмов. Там алгоритм сортировки "Multiply and surrender" и всё такое. Вот рекурсивное Фибоначчи вполне оттуда.

[e2e4]

Maslov, вообще-то я привел не дискуссионные утверждения насчет рекурсии, а вполне общепринятые. Подчеркну два тезиса:
1. Любой рекурсивный алгоритм может быть сведен к итерационному, при этом итерационный будет работать эффективнее (как с т.з. быстроты, так и с т.з. затрат памяти);
2. Не всегда сведение рекурсивного алгоритма к итерационному - простой процесс. Некоторые задачи итерационно не решены до сих пор, хотя рекурсивно формулируются очень легко.

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

Отсюда выводы:

Цитата:

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

Да, но ни в коем случае не быстрее итерационных алгоритмов.

Цитата:

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

меньшей кровью, но не меньшей, чем циклы. live with it (c).

И вообще, считаю, что некоторое идолопоклонничество в связи с рекурсией надумано на 100%. Да, некоторые рекурсивные алгоритмы очень красивы. Но еще более они неэффективны.

[Бодигрим]

Maslov в сообщении #255514 писал(а):

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

Если очень хочется считать числа Фибоначчи рекурсивно, то надо брать формулы $F_{2n}=F_{n+1}^2-F_{n-1}^2$ и $F_{2n+1}=F_n^2+F_{n+1}^2$.

e2e4 в сообщении #255525 писал(а):

Maslov, вообще-то я привел не дискуссионные утверждения насчет рекурсии, а вполне общепринятые.
Подчеркну два тезиса:
1. Любой рекурсивный алгоритм может быть сведен к итерационному, при этом итерационный будет работать эффективнее (как с т.з. быстроты, так и с т.з. затрат памяти);
2. Не всегда сведение рекурсивного алгоритма к итерационному - простой процесс. Некоторые задачи итерационно не решены до сих пор, хотя рекурсивно формулируются очень легко.

Как эти два тезиса согласуются между собой?

Для примера: вы можете свести алгоритм Quicksort к более быстрому итерационному?

[e2e4]

Цитата:

Для примера: вы можете свести алгоритм Quicksort к более быстрому итерационному?

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

[Бодигрим]

e2e4 в сообщении #255530 писал(а):

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

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

[Maslov]

e2e4 в сообщении #255525 писал(а):

Maslov, вообще-то я привел не дискуссионные утверждения насчет рекурсии, а вполне общепринятые.

Да я, собственно, тоже.

e2e4 в сообщении #255525 писал(а):

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

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

e2e4 в сообщении #255525 писал(а):

меньшей кровью, но не меньшей, чем циклы

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

-- Вт окт 27, 2009 15:58:19 --

e2e4 в сообщении #255530 писал(а):

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

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

[ИС]

Вопщем у меня получилась такая ситуация, что первая функция вызывает вторую, а вторая первую )))
Так вот в TurboPascal 7.0 возникает ошибка! Грит функция, которую вызывает первая функция не определена =)
Но она определена у меня чуть ниже по тексту. Как разрулить такую ситуацию?

[ИСН]

Определять чуть выше по тексту

[Maslov]

ИС в сообщении #255643 писал(а):

Грит функция, которую вызывает первая функция не определена =)
Но она определена у меня чуть ниже по тексту. Как разрулить такую ситуацию?

Ключевое слово forward Вам поможет.