Рекурсивные и итерационные алгоритмы

Я реализую алгоритм Евклида для поиска НОД (наибольшего общего делителя) двух целых чисел.

Даны два примера реализации: рекурсивная и итеративная. http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations

Мой вопрос:

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


recursion iteration
person Martin Konecny    schedule 14.04.2010    source источник
comment
stackoverflow.com/questions/478570/recursion-or-iteration   -  person N 1.1    schedule 15.04.2010

Ответы (2)


arrow_upward
4
arrow_downward

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

person Earlz    schedule 14.04.2010

arrow_upward
0
arrow_downward

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

Рекурсия, возможно, более прекрасна в математическом смысле, но если вы чувствуете себя более комфортно с итерацией, просто используйте ее.

person Matti Virkkunen    schedule 14.04.2010