Recursion: Palindromic Primes

Question

I need to create a recursive function to find all palindromic primes between two numbers. The trick is not to use any for of loop or iteration at all. As a beginner to programming I struggle with recursion and have managed to write the program with loops as:

def palindrome(startpoint,endpoint):

    print("The palindromic numbers are:\n")
    num = ''
    inverted = ''
    for i in range(startpoint+1,endpoint):
        num = str(i)

        for j in range(len(num)-1, -1, -1):
            inverted += str(num[j])

        if (num == inverted):
            print(num)
        num = ''
        inverted = ''


def main():

    startpoint = eval(input("Enter the starting point N:\n"))
    endpoint = eval(input("Enter the ending point M::\n"))
    palindrome(startpoint,endpoint)

main()    

I've been trying to write this program recursively but with no luck.

Do I first treat the numbers as strings and check if they are palindromes like this?

def palindrome (str):
   if str == "":
      return str
   else:
      return palindrome (str[1:]) + str[0]

Then check for prime numbers like this:

def prime(n):

if n%2 == 0:
    return False
else: 
    return True

I'm still trying to work this stuff out, any help would be appreciated:)

Answer 1

The general approach to writing a recursive function:

• Handle the simple cases.
• Simplify the problem and call yourself again.

For a function that returns true/false, there will be 3 conditions: you know the answer is true, you know the answer is false, or the problem is still too complicated.

Take the example of the palindrome. You know it's false if the first character and last character don't match. You know it's true if the length of the string is 1 or less. And since you've already checked the first and last character, you can remove those from the string to simplify the problem.