CODEWITHSUNDEEP
pythonrecursion
ASm
ASm

Reputation: 389

Recursively checking if a list is a palindrome in python

I know the beautiful one liner you can use in Python to determine if some input string is a palindrome, however, I want to be able to check if a list is a palindrome, e.g. [1,2,2,1] should return True and [1,2,3,4] should return False. I am passing the function list_palindrome three parameters - the list to check, the index of the first element, and the index of the last element.

So far I have:

def is_mirror(my_list,i1,i2):
    if len(my_list) <= 1:
        return True
    else:
        if my_list[i1] == my_list[i2]:
            return is_mirror(my_list[i1:i2],i1,i2)

But I am getting a IndexError: list index out of range, I think the base case is correct, however my logic is flawed for the recursive call. Any help as to how I can fix this?

Upvotes: 0

Views: 5466

Answers (4)

Shubhika Shree
Shubhika Shree

Reputation: 1

List = []

n = int(input("How many numbers of elements: "))

for i in range(n):
    
    ele = int(input("ENTER THE ELEMENT: "))
    List.append(ele)
print(List)
print(List[::-1])

if List == List[::-1]:
     print("The list is a palindrome")
else:
     print("The list is not a palindrome")

Upvotes: 0

mohan3d
mohan3d

Reputation: 245

You can use slice in python like this way.

def isPalindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and isPalindrome(s[1:-1])

Test:

>>> isPalindrome([1, 2, 3, 4])
False
>>> isPalindrome([1, 2, 2, 1])
True
>>> isPalindrome([1, 2, 3, 2, 1])
True

or you can avoid slicing and use index. i starts with 0, j starts with len(s) - 1.

Edited. 

def isPalindrome(s, i, j):
    if i == j or j < i:
        return True

    return s[i] == s[j] and isPalindrome(s, i + 1, j - 1)

Test:

>>> isPalindrome([1, 2, 3, 4], 0, 3)
False
>>> isPalindrome([1, 2, 2, 1], 0, 3)
True
>>> isPalindrome([1, 2, 3, 2, 1], 0, 4)
True

Upvotes: 2

Raniz
Raniz

Reputation: 11123

The problem is that you're shrinking the list but not changing the boundary parameters. You should do only one of these.

I suggest you drop the boundary parameters and shrink the list using slicing instead:

>>> def is_mirror(lst):
...   if not lst:
...      return True
...   return lst[0] == lst[-1] and is_mirror(lst[1:-1])
... 
>>> is_mirror([1, 2, 3, 4])
False
>>> is_mirror([1, 2, 2, 1])
True
>>> is_mirror([])
True
>>> is_mirror([1])
True
>>> is_mirror([1, 3, 1])
True

Upvotes: 0

Martin Konecny
Martin Konecny

Reputation: 59681

Here's a recursive approach. The basic premise is that with each recursive step, you check if the first and last elements are equal. If so, chop them off, and pass the sublist into the recursive function again.

You will keep going deeper and deeper into your stack with a smaller and smaller list, until you hit your base case.

def is_mirror(my_list):
    if len(my_list) <= 1:
        return True
    else:
        if my_list[0] == my_list[-1]:
            return is_mirror(my_list[1:-1])
        else: 
            return False

Upvotes: 0

Related Questions