开发者

How can I use recursion to find palindromes using Python?

I've just started exploring the wonders of programming. I'm trying to write a code to identify numeric palindromes. Just looking at numbers and not texts. I'm trying to learn to use recursion here. But I'm just not getting anywhere and I can't figure out what's wrong with it.

My idea was to check first string vs the last, then delete these two if they match, and repeat. Eventually there'll be nothing left (implying it is a palindrome) or there will be a couple that doesn't match (implying the reverse).

I know there are better codes to finding palindromes in but I just wanted to try my hand at recursion.

So what's wrong?

def f(n):
    global li   
    li=list(str(n))
    if (len(li)==(1 or 0)):
        return True
    elif li[len(li)-1]==li[0]:
        del li[0]
        del开发者_运维问答 li[len(li)-1]
        if len(li)==0:
            return True
        if len(li)>0:
            global x
            x=''.join(li)
            str(x)
            f(x)
    else:
      return False

Thanks in advance!


A few comments

  • Why are x and li globals? In recursion, all variables should be local.
  • Why are you converting back and forth between str and list? You can subscript both of them
  • You need to return the result of your recursive call: return f(x)

Try these suggestions, and see how it works out.


Before looking into it too much, if (len(li)==(1 or 0)): doesn't do what you're expecting it to do. (1 or 0) will always evaluate to 1.

You probably want:

if len(li) in (1, 0):


There are a couple of problems with your solution. Let me analyse them line by line.

  1. You don't need global statements if you don't intend to change variables outside of function scope. Thus, I removed two lines with global from your code.

  2. li=list(str(n)): casting a string to a list is unnecessary, as a string in Python has a similar interface to an immutable list. So a simple li = str(n) will suffice.

  3. if (len(li)==(1 or 0)):: although it looks OK, it is in fact an incorrect way to compare a value to a few other values. The or operator returns the first "true" value from its left or right operand, so in this case it always returns 1. Instead, you can use the in operator, which checks whether the left operand is an element of a right operand. If we make the right operand a tuple (1, 0), all will be well. Furthermore, you don't need parentheses around the if statement. You should write: if len(li) in (1, 0):

  4. elif li[len(li)-1]==li[0]: is fine, but we can write this shorter in Python, because it supports negative list indexing: elif li[-1] == li[0]:

  5. Because we don't use lists (mutable sequences) because of point 2., we can't do del li[0] on them. And anyway, removing the first element of a list is very inefficient in Python (the whole list must be copied). From the very same reason, we can't do del li[len(li)-1]. Instead, we can use the "splicing" operator to extract a substring from the string: li = li[1:-1]

  6. if len(li)==0: is unnecessary long. In Python, empty strings and lists resolve to False if tested by an if. So you can write if not li:

  7. if len(li)>0:: You don't have to check again if li is not empty -- you checked it in point 6. So a simple else: would suffice. Or even better, remove this line completely and unindent the rest of the function, because the body of the if in 6. contains a return. So if we didn't enter the if, we are in the else without writing it at all.

  8. x=''.join(li): We don't need to convert our string to a string, because of the decision made in 2. Remove this line.

  9. str(x): This line didn't do anything useful in your code, because str() doesn't modify its argument in place, but returns a new value (so x = str(x) would have more sense). You can also remove it.

  10. f(x): This is a valid way to call a recursive function in Python, but you have to do something with its value. Return it perhaps? We'll change it to: return f(li) (as we don't have an x variable any more).

We end up with the following code:

def f(n):
    li = str(n)
    if len(li) in (1, 0):
        return True
    elif li[-1] == li[0]:
        li = li[1:-1]
        if not li:
            return True
        return f(li)
    else:
        return False

It's almost what we need, but still a little refinement can be made. If you look at the lines if not li: return True, you'll see that they are not necessary. If we remove them, then f will be called with an empty string as the argument, len(li) will equal 0 and True will be returned anyway. So we'll go ahead and remove these lines:

def f(n):
    li = str(n)
    if len(li) in (1, 0):
        return True
    elif li[-1] == li[0]:
        li = li[1:-1]
        return f(li)
    else:
        return False

And that's it! Good luck on your way to becoming a successful programmer!


Split the whole show out into a list, then just:

def fun(yourList):
    if yourList.pop(0) == yourList.pop(-1):
        if len(yourList) < 2:
            return True # We're a palindrome
        else:
            return fun(yourList)
    else:
        return False # We're not a palindrome

print "1234321"
print fun(list("1234321")) # True
print "6234321"
print fun(list("6234321")) # False


def palindrome(n):
    return n == n[::-1]


It's hard to tell what you intend to do from your code, but I wrote a simpler (also recursive) example that might make it easier for you to understand:

def is_palindrome(num):
    s = str(num)
    if s[0] != s[-1]:
       return False
    elif not s[1:-1]:
       return True
    else:
       return is_palindrome(int(s[1:-1]))


number = int(raw_input("Enter a number: "))

rev = 0
neg = number

original = number


if (number < 0):
    number = number * -1

else:

    number = number

while ( number > 0 ):

     k = number % 10

     number = number / 10

     rev = k + ( rev * 10 )

     if (number < 1):
         break

if ( neg < 0 ):
    rev =  ( rev * -1)

else:

    rev = (rev)

if ( rev == original):

    print "The number you entered is a palindrome number"

else:

    print "The number you entered is not a palindrome number"

This code even works for the negative numbers i am new to programming in case of any errors dont mind.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜