LINUX.ORG.RU

Дайте задач по рекурсии

 ,


0

2

Вот хочу порешать задач по рекурсии. Может посоветуете чего-либо почитать? Желательно, чтобы решить задач из этого топика

★★★★★

Последнее исправление: cetjs2 (всего исправлений: 4)

Ответ на: комментарий от crowbar

мне пацаны говорят, что надо для лекций LISP учить.

int13h ★★★★★
() автор топика

Дай мне задач по рекурсии, и тогда я дам тебе задач по рекурсии.

rand
()
Ответ на: комментарий от int13h

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

Zenom ★★★
()

Тебе сложных или так? Съешь с stdin'а в дерево индентированные строки по типу питоновского лаяута, посчитай для каждого уровня сумму длин строк, отобранных по динамическому критерию. Нарисуй в двумерном массиве произвольную замкнутую кривую, закрась область в рандомной точке. Вот здесь еще интересные задачи есть.

arturpub ★★
()

Реализовать свой класс натуральных чисел вроде

data Nat = Zero | Succ Nat

Написать сложение, вычитание, умножение, деление, возведение в степень. Построить через натуральные целые числа, написать арифметику для них. Из них сделать рациональные, тоже с арифметическими операциями.

Реализовать List с основными функциями вроде map, zip, foldl/foldr, filter

Реализовать какое-нибудь сбалансированное дерево поиска

BlackHawk
()

Задача: преобразовать выхлоп sax/expat парсера в древовидную структуру, например для питона — словарь.

anonymous
()

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

anonymous
()
Ответ на: комментарий от anonymous

Удобный и красивый нерекурсивный обход того же дерева поиска в студию

BlackHawk
()
Ответ на: комментарий от anonymous

банально - факториал. Рекурсией - строка. Итерацией - больше чем строка. Или я не прав?

int13h ★★★★★
() автор топика
Ответ на: комментарий от PolarFox

я его еще в 7-м классе на паскале писал - пройдено.

int13h ★★★★★
() автор топика

Да, и вообще, по сути, на рекурсивные алгоритмы тратится больше ресурсов(cpu/mem), так?

int13h ★★★★★
() автор топика
Ответ на: комментарий от anonymous

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

Zenom ★★★
()
Ответ на: комментарий от int13h

Это если рекурсия хвостовая, но компилятор ее не умеет оптимизировать. Иначе все равно придется эмулировать рекурсивный вызов сохранением какого-то состояния.

BlackHawk
()
Ответ на: комментарий от BlackHawk

если рассматривать immutable структуры, то случаев всего 4, которые сводятся к двум введением простого хелпера. Но это не так оптимально как mutable.

qnikst ★★★★★
()
Ответ на: комментарий от swwwfactory

кто-нить по русски может объяснить, почему names in funs это что-то необычное, а не то, что в нормальных языках испокон веков есть?

qnikst ★★★★★
()

S-Exp научись вычислять. Очень просто.
На Python'е с использованием простой рекурсии за минут 40 напишешь я думаю.

deterok ★★★★★
()
Ответ на: комментарий от qnikst

Это новшество ввели для анонимных функций (пока в альфе - выход ожидается в марте). Можно ссылаться внутри анонимной функции на саму себя без извратов.

 1> F = fun Fact(0) -> 1; 
              Fact(N) -> N * Fact(N - 1) 
          end.  §
   #Fun
   2> F(10).
   3628800

Which is a zillion times better than the old way.

swwwfactory ★★
()
Последнее исправление: swwwfactory (всего исправлений: 1)
Ответ на: комментарий от swwwfactory

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

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

Это семейство называется «ML programming language family», Миранда появилась через десять лет, а Окамль и вовсе через двадцать после появления оригинального ML'я.

aedeph_ ★★
()
Ответ на: комментарий от BlackHawk

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

Зачем ты проецируешь свою надопортянку на надоязычке на реальный мир? Ну заменил ты реальный мир своим жава-мирком - молодец, только когда балаболишь не забывай упоминать, что - «это работает только в моём жабамирке».

anonymous
()
Ответ на: комментарий от swwwfactory

Крута, ещё лет 50-60 инноваций и дагонит однострочник на сишке. А ещё лет через 100-150 оно перестанет тормазить и будет способно на что-то чуть большее, чем обычная пускалка уровня xargs для всяких неосиляторов. А ещё лет через 200 его недосинтаксис догонит компактность сишки.

anonymous
()
Ответ на: комментарий от int13h


Да, и вообще, по сути, на рекурсивные алгоритмы тратится больше ресурсов(cpu/mem), так?


так, и первым закончится стек

metawishmaster ★★★★★
()
Ответ на: комментарий от Zenom

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

Рекурсия неэффективна, и потому использовать ее будет только криворукий дебил.

В любых серьезных conding standards рекурсию вообще явным образом жестко запрещают. Смотри, как в NASA программируют:

http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

anonymous
()

Вот хочу порешать задач по рекурсии. Может посоветуете чего-либо почитать?

почитай как решать задачи по рекурсии

lazyklimm ★★★★★
()

Как вариант - напишите программу, для решения задачи с рекурсией.

RiseOfDeath ★★★★
()
Ответ на: комментарий от anonymous

Да, косяк. http://pastebin.com/74bVDzHV
Примерно одинаково они работают

10 vertices

Benchmark           Mode Thr     Count  Sec         Mean   Mean error    Units
c.d.b.Graph.bfs     avgt   1        10    1      400.281        2.857    ns/op
c.d.b.Graph.dfs     avgt   1        10    1      380.131        4.241    ns/op

1000 vertices
Benchmark           Mode Thr     Count  Sec         Mean   Mean error    Units
c.d.b.Graph.bfs     avgt   1        10    1  7735569.455    26565.091    ns/op
c.d.b.Graph.dfs     avgt   1        10    1  7676563.842    73305.293    ns/op
BlackHawk
()

Почитай Little Schemer, там всё с рекурсиями.

mentalmenza
()

напиши конвертер bencode -> json

IvanR ★★★
()
15 июля 2015 г.

компилятор чего-нибудь в s-выражения, конвертер json в что-нибудь. если говорить про олимпиадные, то поищи нетривиальных задач на рекурсию(например на графы, где как-то используется dfs) где-нибудь на кодефорсес.

f1u77y ★★★★
()
Ответ на: комментарий от swwwfactory

а мне и так норм.

F = fun(_, 0) -> 1; (F,N) -> N *F(F,N-1) end.
да и вообще, с аккумулятором лучшеé. во всех смыслах
F = fun(_, 0, A) -> A; (F, N, A) -> F(F, N-1, A*N) end.

anonymous
()
Ответ на: комментарий от PolarFox

Если рекурсия хвостовая, то нормальный компилятор сводит её к циклу.

а еще более нормальный этот цикл разворачивает

unt1tled ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.