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

sicp

Ты, я смотрю, уже справился.

не, я серьезно - надо.

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

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

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

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

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

data Nat = Zero | Succ Nat

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

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

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

B+ дерево. Или Red-Black

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

В red-black надо кучу случаев разбирать. В целях разобраться с рекурсией лучше AVL или treap

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

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

В треде уже несколько сообщений, но ещё никто не предложил факториал?

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

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

(apply * (range 1 (inc n)))

Ни рекурсий, ни итераций ☺

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

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

http://projecteuler.net/

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

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

DOM/HTML-парсер

посмотри свежайшие новшества классического примера в эрланге:

http://joearms.github.io/2014/02/01/big-changes-to-erlang.html
раздел Names in Funs

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

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

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

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

 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.

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

лет эдак 20

лисп наверное?

ну тогда можно с разморозкой поДЗдравить :)

если указатели - то не считается...

все семейство вытекшее из миранд и окамлов..

f = let foo 0 = 1
        foo x = x * foo (pred x)
    in foo x

λ> f 10
3628800

вроде 1 в 1..

А вот как-то так можно убедиться, что рекурсивный алгоритм может быть эффективнее нерекурсивного http://pastebin.com/zMPR3wcF

Читай это сообщение

Кстати, фибоначчи уже советовали?

Ещё есть классическая задача 8 ферзей

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

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

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

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

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

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

А в европе нет форумов по около-cs -шной тематике?

к чему это, анон?

Нерекурсивная реализация кривая.

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

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

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

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

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

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

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

Да, косяк. 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

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

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

Горлянский С. П. Решение задач на языке программирования Лисп. - 2014 - 792 с.

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

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

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.

http://www.cs.uu.nl/research/techreps/repo/CS-2012/2012-001.pdf

Только это сложная задача. Думать будешь дня 2 минимум.

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

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