Есть ли разница во времени между рекурсивным и итеративным подходом?

Question

Мне известно, что у нас есть разница в сложности пространства между рекурсивным и итеративным алгоритмом.Но есть ли у нас различия в сложности времени между ними?Например: если у меня есть программа, которая рекурсивно подсчитывает количество узлов в списке, и затем я реализую ту же программу как итеративную, у меня будет какая-либо разница в ее сложности по времени, т.е. O (n)?Спасибо

Answer 1

Краткий ответ: нет.

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

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