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

здрасьте.

счас вот случайно наткнулса на следующее:

Код (Text):

1. //пример неправильного решения (Java)
2. int factorial(int number){
3.   if (number == 1){
4.     return 1;
5.   }else{
6.     return number * factorial(number-1);
7.   }

Код (Text):

1. int factorial(int number){
2.   int intermediateResult = 1;
3.   for (int factor = 2; factor <= number; factor++ ){
4.     intermediateResult  = intermediateResult * factor;
5.   }
6.   return intermediateResult;
7. }

что я хочу узнать - действительно ли все так печально с рекурсией для вычисления того же факториала, и прям память жрецца не-подеццки, или же это только в Ява такое? и вообще, разделяете ли вы точку зрения на описанные примеры выше автора?
кстати, это екзампл из того самого "Совершенного Кода" от Макконнела.
спасибо за мнения.

 

varnie

Автор совершенно прав, в этих двух случаях рекурсивное решение далеко не оптимальное.

 

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

 

на том же си это не оправданное расходование стековой памяти. не знаю как в JVM реализованы каллы, но предполагаю, что там так же.

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

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

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

Вообщем хочется сказать, что выбор технических средств зависит от алгоритма и вообще выбор средств зависит от цели.
Я бы никогда не стал кричать, что дельфи всегда гавно, что ни в коем случае нельзя юзать goto и винить рекурсию во всех смертных грехах. К выбору средств надо подходить с мозгами, ведь, даже на самом крутом автомобиле не уедешь, если водить не умеешь.

 

про реализацию на Си прекрасно понятно, что расходуется память под стек при каждом call при рекурсии. согласен.
но вот в упор не понимаю, почему использование рекурсии при вычислении Факториала числа (и чисел Фибоначчи тоже) сложно для понимания.

в моем вопросе была сделана адресация вопроса по бОльшей части Яваистам. неужели это а-ля "табу" в мире Ява не юзать рекурсию? спрашиваю потому что я любознательный.

 

Отойдем от факториала. А перейдем к другим алгоритмам. Рекурсия не оптимальна. Ее можно заменить циклом, но при этом логика программы может усложниться. Это может гразить реализацие тогоже стека толкьо програмно нежеле чем аппоратно сейчас.
Рекурсия жрет память из стека. Тратиться время на вызов процедуры.

Факториал для возврата в процедуру которая вызвала нужно сахронить адресс это 4(8) байт на вызов. Плюс сохронение состояние переменных зависит от того сколько используется при вычислении факториала тоже 4(8) байт. Сохронение регистров при входе в процедуру в зависимости от оптимизации. Часто используется pusha popa тогда
6*4(8)байт
К примеру факториал 10! получается 10*4*10 - во времена гигобайт это копейки. Стек тем и хорош что память в нем не все время задейстоввана. Как только вычисления прекращаются переменные высвобождаются
А вот время на вызовт тратиться много времени на сохронение состояние. Как видно для факториала и ряда других алгоритмов не целесобразно использовать рекурсию.
Но для других алгоритмов это не совсем не так.

 

Great

Ресурсы на самом деле очень часто не так уж критичны. Существует огромный класс приложений, где операции ввода-вывода занимают в разы больше процессорного времени, чем собственно вычисления. В частности - это практически вся автоматизация учёта на производстве. Там проще сервер помощнее поставить, чем напрягать программистов на написание и тестирование супероптимизированного запроса, чтобы за день секунду серверного времени сэкономить.

Больше того, в реальности лучше не считать факторил так, как делает Макконел. Насколько я знаю, в целые 32-битные числа укладывается не так много факториалов, так что проще и дешевле однажды составить таблицу факториалов и выбирать из неё готовые значения.

Более того, Delphi и VCL почти всегда - рулез. Просто потому что экономит время и нервы разработчика. Лично мне было бы очень скучно и вломы общаться с сервером БД галимыми библиотечными вызовами вместо кавайненьких компонентиков, которые куда меньше утомляют руки, глаза и мозги.

В ныне популярных языках goto - наименее безумный способ выйти из нескольких вложенных циклов. Хотя некоторые странные люди рекомундуют в таких случаях швыряться исключениями, мы их слушать не будем.

 

varnie

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

 

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

 

Pavia
благодарю за такой развернутое пояснение. освежил мозг
CyberManiac, Great
делфи делфей, но не к месту она здесь ИМХО упомянута.

вопрос касаемо (не)приемлимости применения рекурсии в Явовских прогах остается открытым.

 

Грустно, девушки..

CyberManiac и Great, упаси вас господь когда-нибудь вычислять рекурсивно определитель для матрицы большего размера, чем 2x2! За такое высказывание на экзамене выгоняют без разговора.

varnie

Речь идет не о понимании, а об эффективности. Рекурсивное вычисление чисел Фибоначчи - в отличии от прямого - дает экспоненциальную сложность. В численных методах экспоненциальная сложность равносильна смерти.

Насчет Явы: от языка это не зависит. Для нее действуют те же самые правила, что и для С, VB и т.д.

 

Pavia

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

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

 

Stiver

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

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

C чего бы вдруг? Число операций сложения с рекурсией точно такое же, как без рекурсии. Если накладные расходы на рекурсию запредельные - в том вина исключительно жабы, в нормальных компилируемых и интерпретируемых языках всё достаточно хорошо, чтобы рекурсию использовать.

 

varnie

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

CyberManiac

Я бы не доверил тебе писать код инициализации ядерного реактора, старта шатла или обслуживания транзакции в банковской сфере.
http://kholeg.spaces.live.com/blog/cns!D006ED9CB32B0F60!152.entry
http://bugtraq.ru/library/programming/badcode.html

Макконел затрагивает проблемы в целом реализации любого проекта, ибо нужно знать немного больше чем просто язык программирования при создании проекта. Нужно набить немало шишек, чтобы в дальнейшем понять простые истины описаные Макконелом. Книга написана явно не для новичков - можно знать что такое SMM режим работы процессора, зачем нужны movntq или prefetch инструкции, уметь перепрошивать биос и работать с винчестером через порты, НО писать отказоустойчивый на порядок сложнее.

Примеры - пожалуйста запустите Касперского 7.хх на чековой винде

 

Трудоемкой? Вычисление определителя получается из процедуры решения линейных систем удалением трети кода.. и получается алгоритм с O(N^3) операций в то время, как рекурсивный алгоритм выполняет O(N!) операций... и миллисекунды очень быстро превратятся в секунды.. and so on

 

CyberManiac

Ага, теперь я понял, где затык Постараюсь объяснить подробнее.

Дело в том, что когда говорят "заменить рекурсию прямым вычислением", обычно не имеют в виду "тупо переделать рекурсию в цикл". Речь идет о замене алгоритма, рекурсивного - на равноценный, но не содержащий рекурсии. Как правило этот альтернативный алгоритм имеет более низкую сложность. Смотрим на примерах:

1) Вычисление определителя

Я не знаю, где и кто учил ваших физиков. Но рекурсивный метод дает сложность O(2^n) (про обозначение "большое О" читать здесь). Легко представить, что случится, если мы возьмем например n = 10^6 - а именно никакого времени не хватит. Поэтому определители считаются разложением матрицы на две треугольные A=L*R, определители которых в свою очередь вычисляются простым перемножением диагональных элементов. Само разложение имеет сложность O(n^3), разница, думаю, очевидна.

2) Числа Фибоначчи

Рекурсивное вычисление дает снова O(2^n), видно прямо из формулы f_n = f_(n-1) + f_(n-2). Если же считать снизу вверх, то получим линейное время O(n). А можно еще и прямо в формулу подставить..

Основная задача профессионального обучения - вовсе не заставить человека вызубрить команды ассемблера или прерывания с их параметрами. И даже не научить писать драйверы под какую-то систему. Глобальная задача только одна - научить человека алгоритмам и их применению. Поэтому не стоит показывать определенную технику на заведомо для нее неподходящем примере. В лучшем случае читающий посмеется или пойдет на форум искать правду, а в худщем ведь поверит! И получится потом "программист", пишущий экспоненциальный код в надежде на компилятор и быстродействие машины. Приятно видеть автора, понимающего это.

В заключение два классических смертных греха для математика-числовика:
1) Уже названное рекурсивное вычисление определителя (про выгнать с экзамена была не шутка, наблюдал)
2) Решение системы Ax=b путем инвертирования матрицы и умножения с b (желающие могут подумать, почему )

 

мож этот древний как мамонт, экземпель будет к месту?

Код (Text):

1. {$apptype console}
2. program Qsort;
3. {************************************************}
4. {                                                }
5. { QuickSort Demo                                 }
6. { Copyright (c) 1985,90 by Borland International }
7. {                                                }
8. {************************************************}
9.  
10. { This program demonstrates the quicksort algorithm, which      }
11. { provides an extremely efficient method of sorting arrays in   }
12. { memory. The program generates a list of 1000 random numbers   }
13. { between 0 and 29999, and then sorts them using the QUICKSORT  }
14. { procedure. Finally, the sorted list is output on the screen.  }
15. { Note that stack and range checks are turned off (through the  }
16. { compiler directive above) to optimize execution speed.        }
17.  
18. const
19.   Max = 33553924;
20.  
21. type
22.   List = array[1..Max] of Integer;
23.  
24. var
25.   Data: List;
26.   I: Integer;
27.  
28. procedure QuickSort(var A: List; l, r: Integer);
29. var
30.   i, j, x, y: integer;
31. begin
32.   i := l; j := r; x := a[(l+r) DIV 2];
33.   repeat
34.     while a[i] < x do i := i + 1;
35.     while x < a[j] do j := j - 1;
36.     if i <= j then
37.     begin
38.       y := a[i]; a[i] := a[j]; a[j] := y;
39.       i := i + 1; j := j - 1;
40.     end;
41.   until i > j;
42.   if l < j then QuickSort(a, l, j);
43.   if i < r then QuickSort(a, i, r);
44. end;
45.  
46. begin {QSort}
47. //  Write('Now generating 1000 random numbers...');
48.   Randomize;
49.   for i := 1 to Max do Data[i] := Random(-1);//30000);
50.   Writeln;
51.   Write('Now sorting random numbers...');
52.   QuickSort(Data, 1, Max);
53. //  Writeln;
54. //  for i := 1 to 1000 do Write(Data[i]:8);
55. end.

Алгос слегка модифицированый, дабы его можно было легко реверснуть на другой ЯВУ.

Так как насчот рекурсивно отсортировать 128 метров, на упомянутой к месту Java?
Хотелось бы посмотреть во скока псевдо-байт её уложит компиль, на оптимизацию, да и вообще интересно провести краш тестирование, гомосечного JRE движка от SUN..

зы: Ничего не понимаю в рекурсии, и не собираюсь

 

прогон алгоритма, взятого здесь для N = 1024*1024*64 результаты:

п*письками будем чтоли меряцца? 128 мб прогоню после тебя только

 

Код (Text):

1. function GetTickCount:Cardinal;
2. //скопипасшено с kernel32.dll
3. asm
4.   mov         edx,07FFE0000h
5.   mov         eax,[edx]
6.   mul         [edx][04]
7.   shrd        eax,edx,018h
8. end;
9.  
10. var time : cardinal;
11.  
12. begin {QSort}
13.   Randomize;
14.   for i := 1 to Max do Data[i] := Random(-1);
15.  
16.   time := GetTickCount;
17.   QuickSort(Data, 1, Max);
18.   time := GetTickCount-time;
19.  
20.   Writeln(time);
21. end.

получаю значение ~16000

на джаве их сосать не пересосать

 

bugaga
мы отошли от топика, заметь я где-то выше разве говорил что квиксорт в джаве выигрывает? все что меня интересует я изложил в посте #1. а ты устроил детские игры, не упустив шанса закидать яву помидорами. я этот топик не для холиваров заводил и тестилки мне неособо здесь интересны. (были бы интересны, завел бы отдельный топик).

зря я поддалса на твою провокацию.
короче, вот прогон явовского исходника (см. выше) для N = 33553924 (т.е. ~31 MB):

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