Пространственная сложность рекурсивного алгоритма

Question

Меня спросили на собеседовании, эффективный способ решить проблему проверки паллиндром.

Теперь я могу сделать две вещи:

1. , начиная с I = 0 до I = п/2 и сравнение ITH и н-г-й символ равным.
2. Я могу использовать рекурсию, чтобы проверить, являются ли первые и последние одинаковыми, а остальная часть строки - паллиндром.

Вторая рекурсивная. Мой вопрос в том, какова разница в пространственной сложности рекурсивных и нерекурсивных версий алгоритма?

Answer 1

Есть прочитанный на

1. http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
2. Recursion or Iteration?

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

Но если рекурсивная функция является последней строкой вызова (хвостовая рекурсия), то дополнительного штрафа нет.

Это, конечно, оба алгоритма одинаковы.

Answer 2

Теоретически они имеют одинаковую сложность пространства; это во многом зависит от того, можно ли оптимизировать tail recursion.

Если это так, стек заменяется при каждой рекурсии, поэтому он не несет штраф.