рекурсия - зло ? пример из книги.

Stiver

Не надо путать тёплое с мягким. В начале речь идёт о том, что реализовать один и тот же алгоритм без рекурсии это "Вау!", а с рекурсией - "Фу, кака!"

Это очень сильно зависит от целей обучения. Теоретиков и практиков учат совершенно по-разному. Я занимаюсь исключитенльно практиками.

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

Стоит, стоит. Пример работает? Работает. Рекурсию демонстрирует? Демонстрирует. Что ещё надо?

Если бы "не стоило", обучение ООП было бы в принципе невозможно, т.к. ООП эффективен только в достаточно больших проектах, а в программке на 1 страницу печтаного текста он всегда лишний. И что теперь, для обучения ООП в качестве примера выдавать талмуд на 100 тысяч строк? Спасибо, я лучше по старинке, с классами "просто человек" и "человек с зарплатой". А то если я начну пипл левыми телегами грузить, они тему не поймут, а меня с хлебного места сгонят.

 

Кстати а накой ентот Фебоначе нужен?
varnie
А так как джавистЪ джависту Вообще - мну больше фанат J2ME. Ибо платформа прикольная, размер игрух маленький, PNG-картинке, и часто задействованы алгоритмы/програмные фишки, которые попадают под критерий "Идеального Кода". Видимо ограниченые ресурсы тормозной мобилы, способствуют кодера искать уникальные решения.

К сожалению этого нельзя сказать, про всю ту шизуху, которая творица в J2SE. А все то гуано-мастдайное которое на нем лепиться, не иначе как БЫДЛОкодингом не назовешь. Какой тут нахрен "Идеальный Код" -класс на классе (коих с добрую сотню тысяч), костыль на костыле, зачастую с платформо-зависимыми прокладками в нативные либы. Непонятно накой хрен вообще нужна была эта Java (особено в мобилках, видимо впадлу, native-ARM ресурс было предоставить).

Касаемо римейка QuickSort, прожор памяти не превысил

то есть столько - сколько сожрал статический массив, сама прога корректно отработала с дефолтным размером стека, в 1метр, на p3-1Ghz, RAM 256MB, win2k (swap off)

и да - бенчмаркЪ на джаге, не состоялся - урезаная (до 1.8мб) JRE v1.3 (1метр-бинари, 800кб RT.JAR), *class-ы, не запускает, тока jar-ки (юзаю для запуска пары прог). Ковырять опять этот сакс, чет пока нет желания

 

Это уже от нечего сказать? Эффективность ООП очевидна и без приведения тысяч строк кода, для этого достаточно выбрать верные сущности для объяснения основных механизмов, а уж сколько операции класса будут содержать кода не имеет никакого значения.

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

Кстати, в SQL существуют рекурсивные запросы, которые используется обычно для работы с деревьями. Говорят удобнее, чем всякие Nested Sets

 

W4FhLF

Не, это от непонимания общественностью особенностей процесса обучения людей вида Homo Sapiens, исповедующих в отношении программирования радикально отличную от распространённой здесь идеологию. Чтобы их научить, нужно сперва самому отречься от принципов и предать идеалы. После этого приходит понимание того, как надо учить, чтобы обучаемые в результате за два академических часа худо-бедно могли нарисовать перед комиссией работающую программку вместо построения воздушных замков на тему оптимальности алгоритма. И если для обучения рекурсии пример с факториалом удобен и понятен - этот пример был, есть и будет в учебниках вечно, даже если Макконел на фекалии изойдёт от его неоптимальности.

 

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

 

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

 

varnie

Дело, конечно же, не в рекурсии, а в алгоритме.

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

Пример (erlang):

Код (Text):

1. fib(1) -> 0;
2. fib(2) -> 1;
3. fib(N) -> fib(1, 2, 3, N).
4.  
5. fib(_, Y, N, N) -> Y;
6. fib(X, Y, C, N) -> fib(Y, X+Y, C+1, N).

С точностью до константы и без учёта времени и памяти на обработку больших целых чисел -- O(n) по времени, O(1) по памяти.

 

muxamor
троль детектед

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

 

Об этом пытались все сказать еще в первых постах=)

 

Однако.
Определитель рекурсией, интересно как вы его собрались вычислять?

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

Циклом безусловно можно её заменить, без дополнительных затрат тут всё равно никак. Другой вопрос как оптимальнее это сделать, вот и по дискутировали бы на эту тему, развили бы её, всё полезнее чем бесконечно тереть о факториале, а уж тем более о Delphi (так и не понял с какого боку это здесь). Great ты же модер, не разочаровывай. -)

 

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

 

да. нада будет заценить, как на j2МЕ-мобилах рекурсия пашет (какая нибудь).

ы: Midlet Pascal цуко отстойный - консольного компиля нет :'(

Эта. решыл таки с джагой по-дзенить. Не ф курсе коким ассемблером сие можна собрать? А то мну отстал от жизне.

Код (Text):

1. /*
2.       Java Virtual Machine. Disassembler mode: Normal
3.    Class    File   : "HelloWorldApp.class"
4.   Minor version: 3
5.   Source File  : "hello.java"
6.  
7. #  Segment type:    Imports
8. Class synchronized HelloWorldApp
9. extends java.lang.Object
10. {
11.  
12. # Segment type: Pure code
13.   Method void <init>()
14.   max_stack 1
15.   max_locals 1
16.   {
17. # #line 1
18.     aload_0 # var001_0
19.     invokenonvirtual void java.lang.Object.<init>()
20. # #line 1
21.     return
22.   }
23.  
24. # Segment type: Pure code
25.   Method public static void main(java.lang.String[])
26.   max_stack 2
27.   max_locals 1
28.   {
29. #line   4
30.     getstatic java.io.PrintStream java.lang.System.out
31.     ldc1 "Hello World!"
32.     invokevirtual void java.io.PrintStream.println(java.lang.String)
33. #line   5
34.     return
35.   }

Елке. прям дежа-вю (обычный глюк в матреце) какоето.

вот например, функа выдраная из пакмана

Код (Text):

1. public int randi()
2.     {
3.         seed = (seed * 171) % 30269;
4.         return seed;
5.     }

И то как её оформил BCJ,

который я юзаю (ему JRE не нужна):

Код (Text):

1. # Segment type: Pure code
2. Method public int randi()
3.   max_stack 3
4.   max_locals 1
5.   {
6. # #line 140
7.     aload_0 # var006_0 # CODE XREF: resetMobiles+153
8.     aload_0 # var006_0
9.     getfield int seed
10.     sipush 171
11.     imul
12.     sipush 30269
13.     irem
14.     putfield int seed
15. # #line 141
16.     aload_0 # var006_0
17.     getfield int seed
18.     ireturn
19.   }

Хочу все это. А софт морально устарел, асм-вставки не подерживает. (хотелось-бы на марсианском java-асме покодить).

 

Да довольно просто реализуется кстати. Посмотри гугл обходы графов в глубину и ширину (через стек и очередь соответственно)

 

varnie
Я так полагаю твой интерес к рекурсии в Жабе сводится к определению накладных расходов на использование рекурсии. Насчет непредсказуемого использования памяти рекурсией несоглашусь - оно вполне даже предсказуемое.

Стоимость ресурсов потреблямых рекурсией складывается из:
1. Накладных расходов на вызов этой самой рекурсии
2. Размеру локальных переменных в этой самой рекурсивной процедуре
3. Расходу на инициализацию этих самых локальных переменных если надо

И все это помноженное на уровень рекурсии.

В твоем примере с факториалом расходы памяти в рекурсивном вызове относительно невелики, что в Жабе, что в С, другое дело что он неоптимален. Это имеет отношение скорее не к рекурсии а к тому, что если в программе меньше букв, то это совсем не значит, что она быстрее.

Кто-то считает, что от рекурсии нужно уходить, заменяя рекурсивные вызовы итеративными, я с ними не согласен.

И Макконнел в начале своего "Совершенного кода" правильно писал, что утверждение "Эта версия программы работает предположительно быстрее той" неверно.

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

 

Пожуй булку с йадом, может полегчает.

Не, не, не останавливайтесь Продолжайте в том же духе, очень весело читать, вас так здорово прет. Когда же перейдем к фракталам и деревьям?

 

в общем довольно длинный дискусс для такой темы)))))

 

Зря вы тут войны развели... Рекурсия на мой взгляд имеет потребность в осознанном применении... Надо рассматривать ее не как прием кодинга, а как часть алгоритма...

Я думаю, что алгоритмы нерекурсивного обхода деревьев тоже имеются в природе

 

random

Реализацией своего стека, сэкономив на call и сохранении регистров. Но вот вопрос действительно ли это стоит свеч, ввиду современной архитектуры кэша и т.д. Тут зависит и от задачи. Вот у меня недавно было фиксированное дерево, то есть его узлы не менялись. Просто расположил это дерево в плоском массиве, и в обычном цикле его обходил. Но вот для динамического дерева делаю рекурсию, к тому же от переполнения стека всё равно врядли уйти. Так какой смысл? Ну а с факториалом всё и так понятно.

 

http://www.wasm.ru/forum/viewtopic.php?id=22176
Здесь есть пример нерекурсивного обхода дерева. Смысл его заключается в том чти при обходе каждого листа дерево перестраивает само себя. На мой взгляд это плохой алгоритм так как он непригоден к использованию в многопоточных системах.

В случае с самодельным стеком в этом самом стеке необходимо хранить указатель на родительскую вершину (4 байта). Глубина стека здесь будет определятся высотой дерева.
Высота сбалансированного двоичного дерева равна log2 N, где N - количество листов дерева.

Допустим размер стека 4096 байт
Так как каждый элемент занимает 4 байта, то всего получаем 1024 элемента

Итак для того, чтобы произошло переполнение нужно чтобы
log2 N >= 1024 - Найдите-ка мне N. Каких оно порядков?
О каком переполнении стека здесь вообще может идти речь?

Вы вообще читаете посты или вы только флудите бестолку

 

Почему это log2 N? Почему не N^2 * sin N?