Алгоритмы сортировки

[Malriser]

Сообщение от Мефала

Зачем столько нервов? Я ведь просто мнение спросила... Перепишу под цикл, если не съедите.


Показалось проще... Но уже почитала про "съедение стэка" и все дела, так что исправлю, спасибо.

Всегда, ВСЕГДА избегай рекурсии если можно сделать циклом.

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

Для вызова функции используются инструкция call для вызова и ret для возврата, связка которых НАМНОГО, НАМНОГО медленнее операторов условного перехода.
К тому же, стек не резиновый, допустим, по умолчанию имеется стек 1 мб.

Пренебрегая занятой областью - мы имеем 1048576 байта, т.е при вложенности рекурсии рядом со значением 262144 у нас произойдет переполнение стека и программа вылетит.

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

Пример: программа входит в рекурсию декрементируя некоторое значение N до тех пор, пока N не станет отрицательным. Программа использует локально-объявленный массив типа int из 100 элементов. Найти N при котором программа вылетит с вероятностью 1, стек равен 1 мб.
Сможешь?)))


---------
Ответ: При N = 2570, пугает? 1 МБ = 1024 * 1024 байт, одна функция занимает в стеке 100 * 4 байт + 4 байт ( адрес возврата ) + 4 байт ( сохранение значения регистра ebp )


Добро пожаловать в реальность, киса

[Stilet]

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

Если говорить о рекурсии как о методике, то это не всегда так. Не пудри человеку моск.

[Malriser]

Сообщение от Stilet

Если говорить о рекурсии как о методике, то это не всегда так. Не пудри человеку моск.

А я не пудрю, я практик, а не теоретик.

Ты заставь скомпилировать компилятор код, чтобы он вызывал функцию через jmp, а возвращался через jmp r32. Да даже на асме никто не будет так реализовывать вызов функций, ибо извращение.

На практике - рекурсия, самое медленное, как можно реализовать алгоритм

При всем уважении, но ТАКОЕ можно объяснить только так, как я описал. И я не пудрю мозги, а то потом удивляются, почему рекурсия вызывает вылет даже при глубине 2570, а при 2500 работает спокойно. А читайте мой предыдущий пост

[Stilet]

Ты заставь скомпилировать компилятор код, чтобы он вызывал функцию через jmp, а возвращался через jmp r32. Да даже на асме никто не будет так реализовывать вызов функций, ибо извращение.

Ты забываешь, что компиляторов существует чуть больше чем 1 )
Например VM Автолиспа рекурсию умеет сворачивать и даже предсказывать.
Так что повторюсь: Не убеждай ТС в том что существует только один путь.

[Serge_Bliznykov]

Виталий, обратите внимание, что обсуждение идёт в ветке "С/C++"
Вы готовы представить пруф - компилятор C/C++, который развернёт рекурсию в цикл? На примере того самого злополучного кода с BubleSort?
В полученном выполняемом файле не будет рекурсии (т.е. вложенного вызова процедурой самой себя)?!!

Не пойму, к чему этот спор? К тому, что мы все не правы, и в каких-то компиляторах (том же Лиспе) нужно использовать рекурсию всегда, вместо всех циклов, пусть компилятор удивится?!

[Stilet]

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