Question

this assignment is about solving problems using recursion. For each question, write a recursive function that solves the problem asked in that question. Your solutions don't have to be efficient, but they do have to use recursion in a non-trivial way. Put all your code in a file called a9.py.

1. Write a recursive function is_palindrome(s) that returns True or False depending on whether s is a palindrome. This is equivalent to returning s == s[::-1].
2. Write a recursive function find_min(a) that returns the smallest value in the list a.
3. Write a recursive functionreverso(a) that returns a new list that reverses the list  a. This is equvalent to returning a[::-1]
4. Write a recursive functiontower(x) where x is a non-negative integer that returns 2**(2**(2**2(**...**2)...) where the number of 2s in the tower is x

   tower(1)
   2
   >>> tower(2)
   4
   >>> tower(3)
   16
   >>> tower(4)
   65536
   

5. Write a recursive function is_prime(n) that returns True or False depending on whether the positive integer n is prime. (A positive integer n is prime if the only positive integers that divide n are n and 1.)

Answer 1

def is_palindrome(s):
    if len(s) <= 1:
        return True
    else:
        if s[0] != s[-1]:
            return False
        else:
            return is_palindrome(s[1:-1])


def find_min(a):
    if len(a) == 1:
        return a[0]
    else:
        small = find_min(a[1:])
        if a[0] < small:
            small = a[0]
        return small


def reverse(a):
    if len(a) == 0:
        return []
    else:
        lst = reverse(a[1:])
        lst.append(a[0])
        return lst


def tower(x):
    if x == 0:
        return 1
    else:
        return 2 ** (tower(x - 1))


def is_prime(n, i=2):
    if n <= 1:
        return False
    elif n == i:
        return True
    else:
        return n % i != 0 and is_prime(n, i + 1)