Pass positions, not smaller lists
In the last step, each call got a shorter copy of the string. For lists there is a cheaper way: keep the whole list and pass along the positions that the call should work on, like putting two bookmarks in the same book.
The function the problem asks for can't take extra positions, so write a small helper that does, and have the main function call it once with the starting positions.
A helper with two bookmarks: it works on the part of the list between them.
Start at both ends: the first position and the last position.
Does [3, 8, 5, 8, 3] read the same both ways?
3
08
15
28
33
4leftright
check(0, 4): 3 and 3 match. Ask check(1, 3) about the inside.
Move 1 of 4
Compare the ends, then go inward
A list reads the same both ways if its first and last values match and the part between them also reads the same both ways. That inner part is the same question, one step in from each end.
If the ends don't match, you already know the answer is no: no need to call again.
Base case: the bookmarks meet or cross: nothing or one value is left, so yes.
Ends differ? answer no right away.
About 500 calls deep: for 1,000 numbers, which is safe in every language.
def check(nums, left, right):
if left >= right:
return True
if nums[left] != nums[right]:
return False
return check(nums, left + 1, right - 1)
def is_palindrome(nums):
return check(nums, 0, len(nums) - 1)