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

Stariy

while(условие) батенька

 

Miller Rabin

Имелось ввиду, конечно же, полное двоичное дерево? В этом случае высота равна log2(N+1). В случае же сбалансированного двоичного дерева однозначно привязать высоту к количеству листьев не выйдет.

 

clone
Красно-черное двоичное дерево всегда сбалансировано. Так что привязать высоту дерева к количеству листов получается вполне. Ну это уже не из области рекурсии. Даже если заменить log2 N на log2(N+1) принципиально от этого ничего не изменится.

Также хотел затронуть тему рекурсивного поиска файлов в подкаталогах. Для того чтобы искать файлы в подкаталогах, используя FindFirst/FindNext необходимо хранить указатель на хэндл поиска родительского каталога (4 байта). это не проблема. Проблема тут в том что эти две функции требуют указатель на структуру WIN32_FIND_DATA, которая занимает довольно много памяти и часто объявляется как локальная (Так как глобальной ее объявлять совсем плохо). А так как при каждом входе в рекурсию резервируется место под новую структуру WIN32_FIND_DATA, то переполнение совершается легко и непринужденно.

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

В данном случае помещение указателя на родительский каталог в стек выглядит очень даже привлекательно. Существует только одна копия WIN32_FIND_DATA которой вполне достаточно и стековой памяти хватает на ОЧЕНЬ глубокий поиск.

 

bugaga
JASMine.
Жасмин рулит пока

 

не понял. Или я тебя не понял, или ты меня. Степень вложенности каталогов может быть любой

 

Stariy

while(условие (GetNextFile(xxxx) == TRUE))
{
TotalSize += GetFileSize(xxxx);
}

Вообще рекурсия ОБЯЗАНА быть ограниченой - собственно об этом Макконел и пишет. Другими словами рекурсия в том виде который приводистя в этом топике жрет стек причем неизвестно до какого предела она это будет делать. Одно дело если это юзермодное приложение, и совсем другое если это KernelMode драйвер. Но это еще пол-беды, рекурсия хороша только там где она адекватна. Вот пример на ассемблере:

Код (Text):

1. Print2Space: call PrintSpace
2. PrintSpace: mov al,20h ; пробел
3. PrintChar: код выводящий символ
4. retn

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

А вот пример еще

Код (Text):

1. PrintChar: код выводящий символ
2. ...
3. if (какое-то условие) сместиться на следующее условие;
4. mov al, 20h
5. call PrintChar
6. ...
7. retn

Тут память стека и ресурсы PrinChar не освобождаются, причем если следующее условие опять будет удовлетворять if (какое-то условие) то мы рекурсивно вызовемм еще раз PrintChar. Одно дело стек, другое дело ресурсы которые выделяет для текущей операции сама PrintChar

 

PROFi
Что такое GetNextFile(xxxx)? Это типа FindNextFile? Или ты ее сам придумал?

Максимум что он подсчитает это размер файлов в текущем каталоге.

 

Miller Rabin

В контексте данного топика вообще речь о "реальных" функциях не идет..

 

хе-хе-хе. Тогда уж вообще проще написать что-нить вроде

Код (Text):

1. DirSize = GetDirSize(xxx);

, если так...

 

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

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

 

Существуют. Работают ничуть не хуже рекурсивных, и я бы не сказал что они сложнее для понимания

 

кстати, никто не пояснит, почему во многих туторах/книгах итд по программированию рекурсивный пример вычисления факториала заранее имеет лишнюю итерацию?
пример на хаскелле:

Код (Text):

1. factorial n = if n == 0 then 1 else n * factorial (n - 1)

зачем нам ждать пока n не станет нулем? разве при n == 1 нельзя возвратить единицу и остановить дальнейшие рекурсивные вызовы?
на С++ куча аналогичных примеров.

 

varnie
Просто считают что 0!=1, так что эта итерация не лишняя.

 

Black_mirror
верно, я забыл...
тогда получается, что неверна следующая реализация:

Код (Text):

1. int factorial(int n) {
2.   int res;
3.   if (n == 1) {
4.     res = 1;
5.   } else {
6.     res = n*factorial(n-1);
7.   }
8.   return res;
9. }
10.  
11. printf("%d", factorial(0)); //ы?

 

varnie
Твоя реализация уйдет в бесконечный цикл, потому что заглушка рекурсии никогда не сработает.

 

Toney
вестимо, что уйдет. я про чтО и говорю.
это не моя реализация, а пример с www.koders.com, коих там предостаточно.

 

Вообще ответ на твой вопрос очень прост. Факториал 0 = 1. Так что эта итерация никак не является лишней, а все алгоритмы которые её не имеют заранее глючные

 

омг... это форум ассемберщиков?
Такое впечатление, что все под "рекурсией" понимают только "вызов процедуры из самой себя", так это только частный случай, думаю многие понимают что call отличается от jmp только запихиванием адреса возврата в стек, а программный стек от аппаратного принципиально ничем не отличается.

Насчет факториала, и любых "рекурсий" вида
proc1: <какойто код работающий c переменной [esp+arg1]>
push <новая переменная>
push exit_proc1 / jmp proc1 ;это типа call
exit_proc1:

Это самый что ни на есть цикл, только с замусориванием стека никому не нужными адресами возврата и старыми значениями переменных. Вообще "рекурсии" где функция вызывает себя один раз - это цикл.
function y(x) {<код>;y(x*(x-1))} - здесь при очередном вызове "x" хранить уже не нада.

А вот там где функции надо вызвать себя хотябы два раза подряд, там уже "настоящая" рекурсия, когда переменные в стеке при первом вызове хранятся для второго вызова
function p(x) {<код>;y(x*0,25);y(x*0,75)} - здесь при первом вызове y(x*0,25) "x" продолжает храниться в стеке чтобы затем вызвать y(x*0,75).

 

GoldFinch
А вот там где функции надо вызвать себя хотябы два раза подряд, там уже "настоящая" рекурсия

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

Код (Text):

1. sub    n, 1
2. push  n
3. call    FibProc
4. add    esp, 4
5. mov   res, eax
6. sub    n, 1
7. push  n
8. call    FibProc
9. add    esp, 4
10. add    res, eax
11. mov   eax, res

говорит об аццкой ламерности кодера, т.к число тактов на вычисление n-ого числа растет экспоненциально и,например, для моего проца (2x1600) для n = 39 составляет ~ 7 секунд

 

а зачем вообще вычислять рекурсивно если есть нерекурсивный алгоритм?