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

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

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

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

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

Ответы

Ответ 1

Прочитайте в

• http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
• Рекурсия или итерация?

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

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

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

Ответ 2

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

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