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

Тема в разделе "WASM.HEAP", создана пользователем varnie, 20 июн 2008.

  1. CyberManiac

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.473
    Адрес:
    Russia
    Stiver
    Не надо путать тёплое с мягким. В начале речь идёт о том, что реализовать один и тот же алгоритм без рекурсии это "Вау!", а с рекурсией - "Фу, кака!"

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

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

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

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

    bugaga New Member

    Публикаций:
    0
    Регистрация:
    1 июл 2007
    Сообщения:
    361
    Кстати а накой ентот Фебоначе нужен?
    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-ки (юзаю для запуска пары прог). Ковырять опять этот сакс, чет пока нет желания :)
     
  3. W4FhLF

    W4FhLF New Member

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

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

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

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.473
    Адрес:
    Russia
    W4FhLF
    Не, это от непонимания общественностью особенностей процесса обучения людей вида Homo Sapiens, исповедующих в отношении программирования радикально отличную от распространённой здесь идеологию. Чтобы их научить, нужно сперва самому отречься от принципов и предать идеалы. После этого приходит понимание того, как надо учить, чтобы обучаемые в результате за два академических часа худо-бедно могли нарисовать перед комиссией работающую программку вместо построения воздушных замков на тему оптимальности алгоритма. И если для обучения рекурсии пример с факториалом удобен и понятен - этот пример был, есть и будет в учебниках вечно, даже если Макконел на фекалии изойдёт от его неоптимальности.
     
  5. Stariy

    Stariy Member

    Публикаций:
    0
    Регистрация:
    22 окт 2003
    Сообщения:
    529
    Адрес:
    Russia
    хм... А вот, к примеру, как можно подсчитать суммарный объем всех файлов в каталоге и вложенных подкаталогах, не используя рекурсию?
     
  6. muxamor

    muxamor New Member

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

    clone New Member

    Публикаций:
    0
    Регистрация:
    4 июл 2006
    Сообщения:
    84
    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) по памяти.
     
  8. Osen

    Osen Рие

    Публикаций:
    0
    Регистрация:
    5 апр 2008
    Сообщения:
    283
    Адрес:
    Париж
    muxamor
    троль детектед

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

    wasm_test wasm test user

    Публикаций:
    0
    Регистрация:
    24 ноя 2006
    Сообщения:
    5.582
    Об этом пытались все сказать еще в первых постах=)
     
  10. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Однако.
    Определитель рекурсией, интересно как вы его собрались вычислять?

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

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

    wasm_test wasm test user

    Публикаций:
    0
    Регистрация:
    24 ноя 2006
    Сообщения:
    5.582
    А что я не того сказал? Я это же и имел в виду, может быть выразил не так.
     
  12. bugaga

    bugaga New Member

    Публикаций:
    0
    Регистрация:
    1 июл 2007
    Сообщения:
    361
    да. нада будет заценить, как на 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-асме покодить).
     
  13. Vilco

    Vilco Vitaly

    Публикаций:
    0
    Регистрация:
    5 мар 2007
    Сообщения:
    190
    Адрес:
    Nsk, Russia
    Да довольно просто реализуется кстати. Посмотри гугл обходы графов в глубину и ширину (через стек и очередь соответственно)
     
  14. Miller Rabin

    Miller Rabin New Member

    Публикаций:
    0
    Регистрация:
    4 янв 2006
    Сообщения:
    185
    varnie
    Я так полагаю твой интерес к рекурсии в Жабе сводится к определению накладных расходов на использование рекурсии. Насчет непредсказуемого использования памяти рекурсией несоглашусь - оно вполне даже предсказуемое.

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

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

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

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

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

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

    muxamor New Member

    Публикаций:
    0
    Регистрация:
    13 июн 2008
    Сообщения:
    20
    Пожуй булку с йадом, может полегчает.

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    в общем довольно длинный дискусс для такой темы:))))))
     
  17. random

    random New Member

    Публикаций:
    0
    Регистрация:
    10 янв 2008
    Сообщения:
    38
    Зря вы тут войны развели... Рекурсия на мой взгляд имеет потребность в осознанном применении... Надо рассматривать ее не как прием кодинга, а как часть алгоритма...
    Я думаю, что алгоритмы нерекурсивного обхода деревьев тоже имеются в природе
     
  18. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    random
    Реализацией своего стека, сэкономив на call и сохранении регистров. Но вот вопрос действительно ли это стоит свеч, ввиду современной архитектуры кэша и т.д. Тут зависит и от задачи. Вот у меня недавно было фиксированное дерево, то есть его узлы не менялись. Просто расположил это дерево в плоском массиве, и в обычном цикле его обходил. Но вот для динамического дерева делаю рекурсию, к тому же от переполнения стека всё равно врядли уйти. Так какой смысл? Ну а с факториалом всё и так понятно.
     
  19. Miller Rabin

    Miller Rabin New Member

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

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

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

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

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

    r90 New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2005
    Сообщения:
    898
    Почему это log2 N? Почему не N^2 * sin N?