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

Pete, ничего экзотического, перепиши обычную быструю сортировку (Хоара), не создавая собственного стека.
И сравни быстродействие эмуляции стека с явной рекурсией. Такой вариант, возможно, окажется быстрее, но ненамного. И даже в этом я не уверен. 

Это сообщение отредактировал(а) Void - 10.6.2006, 18:23

Хм.. Согласен. Пока не встречал ее итерационной реализации без стека. Сравнение этих алгоритмов в скорости, наверное, уже больше зависит от системы. Конечно, отсутствие объявления новых переменных на каждом уровне рекурсии придаст определенное ускорение, хотя, кто знает...
(ЗЫ: мы пока от темы не ушли далеко?  )  

Это сообщение отредактировал(а) Pete - 10.6.2006, 18:45

Ну мне кажется тут такой же "большой" прирост в скорости, что и при использовании

Вместо
 

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

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

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



И еще:


Это Intel C++ 9.0 в режиме максимальной оптимизации.
Не оптимизируйте, и не оптимизируемы будете  

Void, просто говорю, что в справочнике написано, а об "вылезании" там тоже писали  

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

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

Кажется, уже обсуждалось, что статические переменные не могут дать никакого преимущества в скорости перед локальными. 

я это и имел в виду, не так выразился

под статическим массивом я подразумевал массив на стеке (размер известен в compile-time)
как пример можно взять рекурсивную функцию

и эквивалентную ее итеративную с эмуляцией стека

и вызов

тут итеративная выигрывает в используемой памяти (261 против 512 байт) и по количеству команд процессора
(326 против 575 (вывод считаем оной командой; командную реализацию while и if не рассматриваем))
так как любая рекурсивная программа сводится к итеративной, то, как показывает пример, при правильной ее организации она оказывается более эффективной  

Это сообщение отредактировал(а) MAKCim - 12.6.2006, 09:42

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

Результаты:
GCC 3.4.5 (MinGW)

VC 8.0:

Вот такая забавная картина, не находите? 
Так стоит ли заморачиваться с ручной эмуляцией стека ради пары процентов производительности, которые в зависимости от компилятора могут оказаться и на той, и на другой стороне? ИМХО, нет.
В данном случае можно было оценить верхний предел глубины рекурсии, однако выделяя под стек массив постоянного размера мы в любом случае рискуем молчаливо вылететь за его пределы. Используя же динамический массив мы рискуем свести на нет все призрачные преимущества эмуляции рекурсии.