recursive function problem

[qingmui]

I dont know how to start. I learn python by myself, hopefully i can solve this problem.
but i think i need your guys help

A palindrome is a sentence that contains the same sequence of letters reading it either forwards or backwards. For example "racecar". Write a recursive function that detects whether a string is a palindrome. The basic idea is to check that the first and last letters of the string are the same letter. If they are, then the entire string is a palindrome if everything between those letters is a palindrome. When you compare letters, ensure you do it in a case-insensitive way. Use your function in a program that prompts the user for a phrase and then tells whether or not it is a palindrome.

[group256]

Post your code and let us see what you have done up until now.

[cghtkh]

To help you get started, for recursive function, think of
(1) termination condition
(2) each successive step solves a smaller subset of original problem.

In your case, you can solve the problem by checking the first and last
characters, and passing the shorter substring with first and last characters
removed to the recursive function.

[richieking]

Try this fancy one.

def chec(sa):
    data=[]; #make a list
    for x in sa:
        data.append(x.lower()); #pack the result into the list
   
    d1 ,d2 =(data[0], data[-1]);
    if d1 == d2:     #check up the results
        print d1 ,d2 , "are the same";
    else:
        print d1 , d2 , "are not the same"


chec("racecar")
#============== Reuults=============
r r are the same

will do what you wnat i think ;)

[TrustyTony]

And OP must add the recursion?
To only check if things are palindrome is by the way enough to:

def ispalindrome(x): return x == x[::-1]

(The recursive version can be written with same amount of lines)

[d5e5]

And OP must add the recursion?
To only check if things are palindrome is by the way enough to:

def ispalindrome(x): return x == x[::-1]

(The recursive version can be written with same amount of lines)

I like that. It's much shorter than what I was thinking of. However the OP says that palindromes can be sentences as well as single words, so the function perhaps should also remove all punctuation and spaces from the input string before testing it the first time. That way it could handle palindromic sentences such as, "Red Roses run no risk, sir, on nurses order."

[richieking]

Try this fancy stuff:

import time # for time

def chec(sa):
    fd=sa
    for x in range(1, 10): #fancy.... You dont really need this but mmmm
        print ".",         #
        time.sleep(1)      #
    print '\n'               # you can try

    data = []; #make a list
    try:
        for x in sa:
            data.append(x.lower()); #pack the result into the list

        d1, d2 = (data[0], data[-1]);
    except:
        print "Values needed"
    else:
        if d1 == d2:     #check up the results
            print 'Check Results'
            print "-"*30
            print d1.upper(), d2.upper(), 'are the same\n';
        else:
            print 'Check Results'
            print "-"*30
            print d1.upper(), d2.upper(), 'are not the same\n'
    print "You entered:",fd ,'\n\n'

while True:  #
    choice = raw_input("Please enter choice [Enter] or  Q[to quit]: ").lower().strip()#get data
    if choice == "q": #check data
        break; #action
    else:
        try: #exception check
            palin = raw_input("Please enter a Phrase: ")
            chec(palin)
        except ValueError: #catch
            print "Enter phrase to check";
print "Check finished" #final line

Look is fun ok ;)

[TrustyTony]

I like that. It's much shorter than what I was thinking of. However the OP says that palindromes can be sentences as well as single words, so the function perhaps should also remove all punctuation and spaces from the input string before testing it the first time. That way it could handle palindromic sentences such as, "Red Roses run no risk, sir, on nurses order."

Yes unfortunately it takes two lines without being too hackish (replacing assignment with single item loop):

sentence = "Red Roses run no risk, sir, on nurses order."
sentence_clean = ''.join(c.lower() for c in sentence if c.isalpha())
print '%r %s palindrome.' % (sentence, 'is' if sentence_clean == sentence_clean[::-1] else 'is not')

[woooee]

Not recursion, but proof of concept only (and done quickly). Returns zero if it is a palindrome.

def ispalindrome(pal): return sum([0 if x == pal[(ctr+1)*-1] else 1 for ctr, x in enumerate(pal) if ctr < len(pal)/2])

sentence = "Red Roses run no risk, sir, on nurses order."
sentence_clean = ''.join(c.lower() for c in sentence if c.isalpha())
print ispalindrome(sentence_clean)
print ispalindrome("abcdef")

[TrustyTony]

zero is False so may I kindly suggest that you wooee replace sum with not any which has short cut logic. Using generator instead of producing list would be also nicer.
Have to say that your algorithm looks little too FORTRANish for my taste ;)

[richieking]

How do you guys expert a newbie to understand short algorithm like this.????

Are you helping or showing off???
;)

qingmui does not get you guys ;)

[TrustyTony]

We are just entertaining ourself while not giving the answer.

OK, OP:
consider these candidates from simpler to more difficult for recursive algorithm base case:

ispalindrome('')
ispalindrome('a')
ispalindrome('aa')
ispalindrome('ab')
ispalindrome('aba')
ispalindrome('abc')

and consider that
'aa' = 'a'+''+'a'
'ab' = 'a'+''+'b'

means 'aa'[1:-1] = '', which is valid input for ispalindrome function.

[zentraders]

There are literally hundreds of palindrome examples on the web, most using "standard" methods, and some of which I have posted myself. Solutions using recursion are posted in many places on Daniweb as well, for anyone who looks. I am not going to reward the lazy.

[TrustyTony]

There are literally hundreds of palindrome examples on the web, most using "standard" methods, and some of which I have posted myself. Solutions using recursion are posted in many places on Daniweb as well, for anyone who looks. I am not going to reward the lazy.

Your recursive solution link is luckily the Vegaseat solution that I gave in this thread for the very reason it is not recursive. We are trying to make one guy to understand recursion, not to learn copy-paste, I think!

The recursive solution is very simple one liner, I do not think it is necessary to mislead the OP nor to give the solution. If he gets it we can show our cards.

[TrustyTony]

This is also usefull fact for super simplicity of the recursive solution:

>>> 'a'[1:-1]
''

[cute cat]

can you help me!!

I have assignment that told me to write a function 'CheckSmaller' that takes two linked list as input arguments. These linked list contain numbers like this:

num1->3->5->2->NULL (assuming that num1 is pointing to number 352)
num2->4->3->9->1->NULL (assuming that num2 is pointing to number 4391)

The function CheckSmaller should return 1 if num1 points to a linked list which represents a smaller number than the number pointed to by num2 linked list. Otherwise, it returns -1. If both linked list point to exactly the same number, CheckSmaller returns a 0.

int CheckSmaller(Node* num1, Node* num2);

Notice that if two linked lists are:

num1->8->4->2->NULL (assuming that number 1 is 842) and
num2->8->4->3->NULL (assuming that number 2 is 843)
then your function should return 1 since 842 is smaller than 843.

and I want to use Recursion for this function

THANK YOU

Notice:
Hijacking older threads with an unrelated problem is considered bad manners!
Please start your own thread and show some coding effort!

[cute cat]

Please i want it today or tomorrow >__<

[vegaseat]

I am showing this only as a basic example of a recursive function ...

# a typical example of a recursive function
# there is a limit to recursions in Python
# sys.getrecursionlimit() --> usually 1000
# can be changed with
# sys.setrecursionlimit(new_limit)

def palindrome_recursive(s):
    # slicing gets the first and last letter
    first = s[:1]
    last = s[-1:]
    print(first, last, s[1:-1])  # for testing only
    if first != last:
        return False
    # exit condition
    if len(s) < 2:
        return True
    # recursion calls the function from within the function
    # with an adjusted parameter, first and last letter sliced off
    return palindrome_recursive(s[1:-1])

s = "racecar"
print(palindrome_recursive(s))