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

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

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

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

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