递归：回文质数

Question

我需要写一个递归函数，来找出两个数字之间所有的回文质数。关键是不能使用任何的循环或迭代。作为一个编程初学者，我在递归方面有些困难，之前写的程序是用循环实现的，如下：

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()    

我一直在尝试用递归来写这个程序，但一直没有成功。

我是不是应该先把数字当作字符串来处理，然后检查它们是否是回文，比如这样做：

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

然后再检查它们是否是质数，像这样：

def prime(n):

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

我还在努力弄明白这些内容，任何帮助都会很感激：)

Answer 1

写递归函数的一般方法：

• 先处理简单的情况。
• 简化问题，然后再调用自己。

对于一个返回真或假的函数，通常会有三种情况：你知道答案是对的，你知道答案是错的，或者问题还是太复杂。

举个回文的例子。如果第一个字符和最后一个字符不一样，你就知道这个字符串不是回文。如果字符串的长度是1或者更短，你就知道它是回文。而且因为你已经检查过第一个和最后一个字符，所以可以把它们从字符串中去掉，这样就能简化问题了。