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
andli
globals? In recursion, all variables should be local. - Why are you converting back and forth between
str
andlist
? 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.
You don't need
global
statements if you don't intend to change variables outside of function scope. Thus, I removed two lines withglobal
from your code.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 simpleli = str(n)
will suffice.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. Theor
operator returns the first "true" value from its left or right operand, so in this case it always returns1
. Instead, you can use thein
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 theif
statement. You should write:if len(li) in (1, 0):
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]:
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 dodel li[len(li)-1]
. Instead, we can use the "splicing" operator to extract a substring from the string:li = li[1:-1]
if len(li)==0:
is unnecessary long. In Python, empty strings and lists resolve to False if tested by anif
. So you can writeif not li:
if len(li)>0:
: You don't have to check again ifli
is not empty -- you checked it in point 6. So a simpleelse:
would suffice. Or even better, remove this line completely and unindent the rest of the function, because the body of theif
in 6. contains areturn
. So if we didn't enter theif
, we are in theelse
without writing it at all.x=''.join(li)
: We don't need to convert our string to a string, because of the decision made in 2. Remove this line.str(x)
: This line didn't do anything useful in your code, becausestr()
doesn't modify its argument in place, but returns a new value (sox = str(x)
would have more sense). You can also remove it.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 anx
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.
精彩评论