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

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

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

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

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

Прочитайте в

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

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

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

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

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