Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Python

Posted by Dima Mykhaylov
Dima Mykhaylov
19,379 Points

How can I create a recursive Python function to find the longest palindrome?

I was wondering how can I create a recursive python function that takes a single argument which is a string and finds the longest palindrome in that string.

So far, I've created a recursive function that determines if the string is a palindrome, but I'm not sure how to change it so that it detects what the longest palindrome is in a given string if there is one at all. How can this be done?

Current function:

def is_palindrome(s):
  if len(s) < 2:
    return True
  if s[0] != s[-1]:
    return False
  return is_palindrome(s[1:-1])

2 Answers

Steven Parker
Steven Parker
243,266 Points
Steven Parker
Steven Parker
243,266 Points

First, you can simplify "is_palindrome" so it works without recursion. Then use it in the search function.

Then one way you could search for the longest palindrome might be with a strategy like this:

  • if the argument is a palindrome itself, return it
  • otherwise the function could call itself with a slice that removes the last character, saving that result
  • then it could call itself with a slice removing the first character, and also save that result
  • then it could return the longest result from those two recursive calls
Dima Mykhaylov
Dima Mykhaylov
19,379 Points

Thanks for the response. I have simplified "is_palindrome" to work without recursion. So far I have it working to return the argument if it is already a palindrome. I then made an else statement and saved the result of calling the function with a slice removing the first character and a slice removing the last. I'm not quite sure what to do beyond this point.

So far I'm not sure how to do the final step you have suggested which is returning the "longest result from those two recursive calls"?

This is what I have currently:

# function for determining a palindrome
def is_palindrome(s):
  return str(s) == str(s)[::-1]

# palindrome search
def palindrome_search(string):
  # if the argument is a palindrome return it
  if is_palindrome(string) == True:
    print(string)
  else:
    x = palindrome_search(string[:-1])
    y = palindrome_search(string[1:])
  if len(x) > len(y):
    return x
  else:
    return y

print(palindrome_search("Some like cakes, but I prefer pie")) # This should return 'ipreferpi'
Steven Parker
Steven Parker
243,266 Points
Steven Parker
Steven Parker
243,266 Points

You did say you specifically wanted a recursive solution, but recursion is often not the most efficient method.

Solving "...but I prefer pie" takes 4,417 calls of the method, but
solving "...cakes, but I prefer pie" takes 244,269 calls of the method, and
solving "...like cakes, but I prefer pie" takes 4,150,875 calls of the method, and
solving "Some like cakes, but I prefer pie" takes 67,019,601 calls of the method

That took a bit over a minute to compute on the workspace, I'm guessing you just got impatient and stopped it before it finished. :wink:

Dima Mykhaylov
Dima Mykhaylov
19,379 Points

I suppose this just comes to show that recursion is not always the best solution. Thanks for the help.

Steven Parker
Steven Parker
243,266 Points
Steven Parker
Steven Parker
243,266 Points

It looks like you already have the "return the longest result" part correctly. But here's a few hints on other issues:

  • based on the example, you'll need to convert the incoming string to lowercase
  • it also looks like you'll be needing to remove spaces and punctuation
  • the first part needs to return the string instead of print it
  • you don't need to perform "str()" on a string
  • it's not necessary to compare a boolean with "True", just use it directly
  • an "else" is not needed after an "if" which performs a return
Dima Mykhaylov
Dima Mykhaylov
19,379 Points

I've made some changes to the code and it seems to work for shorter strings such as "However, I prefer pie" but when I pass the full string "Some like cakes, but I prefer pie" it doesn't return anything and the program just seems to hang.

Current updated code:

# collect user input
string_for_function ="However I prefer pie"
string_for_function = string_for_function.lower()
string_for_function = ''.join(i for i in string_for_function if i.isalnum())


# function for determining a palindrome
def is_palindrome(s):
  return s == s[::-1]

# palindrome search
def palindrome_search(string):
  # if the argument is a palindrome return it
  if is_palindrome(string):
    return string

  x = palindrome_search(string[:-1])
  y = palindrome_search(string[1:])

  if len(x) > len(y):
    return x
  else:
    return y


print(palindrome_search(string_for_function))

# Declaring 'Some like cakes, but I prefer pie' as the value for 'string for function' and passing that
# to the function 'palindrome_search' should return 'ipreferpi'
Steven Parker
Steven Parker
243,266 Points
Steven Parker
Steven Parker
243,266 Points

See the comment I added to my original answer. :arrow_heading_up: