2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4  След.
 
 Задачки на рекурсию.
Сообщение27.10.2009, 11:48 
Аватара пользователя
Подскажите пожалуйста где можно взять простые задачки для решения которых нужно использовать рекурсию. А то я пока очень плохо составляю алгоритмы использующие рекурсию (

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

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 14:11 
Цитата:
А то я пока очень плохо составляю алгоритмы использующие рекурсию (

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

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

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

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

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

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 14:31 
Аватара пользователя
Мне к зачету нужно будет разобраться с алгоритмами быстрой сортировки и с деревьями. Так вот быстрая сортировка и алгоритмы обхода дерева содержат рекурсию, и мне пока сложно в них разбираться. Вот по этому я хочу прорешать несколько простых задачек чтобы хорошо как же всетаки они работают )

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 15:19 
e2e4 в сообщении #255492 писал(а):
И это здорово. Тем больше шансов составить нормальный, итерационный алгоритм :).
А почему Вы считаете итерационные алгоритмы более "нормальными", чем рекурсивные?

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

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

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 15:25 
Аватара пользователя
(в сторону) Есть такая наука - отыскание наихудших алгоритмов. Там алгоритм сортировки "Multiply and surrender" и всё такое. Вот рекурсивное Фибоначчи вполне оттуда.

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

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

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

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

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

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

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

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 15:42 
Аватара пользователя
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 к более быстрому итерационному?

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 15:47 
Цитата:
Для примера: вы можете свести алгоритм Quicksort к более быстрому итерационному?

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

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 15:52 
Аватара пользователя
e2e4 в сообщении #255530 писал(а):
Я не могу, но доказано, что это возможно, с меньшими затратами памяти и проц. времени. Причем доказано для всех алгоритмов, основанных на рекурсии, а не только для Quicksort. Просто, возможно, до этого еще никто не додумался?

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

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 15:55 
e2e4 в сообщении #255525 писал(а):
Maslov, вообще-то я привел не дискуссионные утверждения насчет рекурсии, а вполне общепринятые.
Да я, собственно, тоже.
e2e4 в сообщении #255525 писал(а):
Любой рекурсивный алгоритм может быть сведен к итерационному, при этом итерационный будет работать эффективнее (как с т.з. быстроты, так и с т.з. затрат памяти);
Ну и что? Любая программа на языке высокого уровня может быть переписана на ассемблер, при этом ассемблерная программа будет работать эффективнее (как с т.з. быстроты, так и с т.з. затрат памяти). Это же не повод отказаться от языков высокого уровня.
Тут нет общего подхода - в каждом случае оценку соотношения затраты-выигрыш надо проводить отдельно.
e2e4 в сообщении #255525 писал(а):
меньшей кровью, но не меньшей, чем циклы
Меньшей. Структуры данных в функциональных языках неизменяемые, поэтому побочных эффектов, которые являются основной сложностью при распараллеливании, просто нет.

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

e2e4 в сообщении #255530 писал(а):
Я не могу, но доказано, что это возможно, с меньшими затратами памяти и проц. времени. Причем доказано для всех алгоритмов, основанных на рекурсии, а не только для Quicksort.
Укажите, пожалуйста, источник.
Дело в том, что при компиляции рекурсивных программ возможны самые разные варианты. В частности, многие компиляторы умеют преобразовывать хвостовую рекурсию в обычную команду перехода; алгоритмы от этого не перестают быть рекурсивными.

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

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 20:44 
Аватара пользователя
Определять чуть выше по тексту :D

 
 
 
 Re: Задачки на рекурсию.
Сообщение27.10.2009, 20:50 
ИС в сообщении #255643 писал(а):
Грит функция, которую вызывает первая функция не определена =)
Но она определена у меня чуть ниже по тексту. Как разрулить такую ситуацию?

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

 
 
 [ Сообщений: 58 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group