Solutions: You can find the file with solutions for all questions here.

## Recursion

### Question 1: Decimal

Write the recursive version of the function `decimal` which takes in `n`, a number, and returns a list representing the decimal representation of the number.

``````def decimal(n):
"""Return a list representing the decimal representation of a number.

>>> decimal(55055)
[5, 5, 0, 5, 5]
>>> decimal(-136)
['-', 1, 3, 6]
"""
if n < 0:
return ['-'] + decimal(-1 * n)
elif n < 10:
return [n % 10]
else:
return decimal(n // 10) + [n % 10]``````

Use OK to test your code:

``python3 ok -q decimal``

### Question 2: Hailstone

For the `hailstone` function from previously, you pick a positive integer `n` as the start. If `n` is even, divide it by 2. If `n` is odd, multiply it by 3 and add 1. Repeat this process until `n` is 1. Write a recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

``````def hailstone_iterative(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.

>>> a = hailstone_iterative(10)
10
5
16
8
4
2
1
>>> a
7
"""
print(n)
if n == 1:
return 1
elif n % 2 == 0:
return 1 + hailstone_iterative(n // 2)
else:
return 1 + hailstone_iterative(3 * n + 1)

def hailstone_recursive(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.

>>> a = hailstone_recursive(10)
10
5
16
8
4
2
1
>>> a
7
"""
print(n)
if n == 1:
return 1
elif n % 2 == 0:
return 1 + hailstone_recursive(n // 2)
else:
return 1 + hailstone_recursive(3 * n + 1)``````

Use OK to test your code:

``````python3 ok -q hailstone_iterative
python3 ok -q hailstone_recursive``````

### Question 3: is_palindrome

Write a recursive solution for the function `is_palindrome` such that it takes in any list and returns True if that list is the same way going forwards and backwards.

``````def is_palindrome(lst):
""" Returns True if the list is a palindrome. A palindrome is a list
that reads the same forwards as backwards
>>> is_palindrome([1, 2, 3, 4, 5])
False
>>> is_palindrome(["p", "a", "l", "i", "n", "d", "r", "o", "m", "e"])
False
>>> is_palindrome([True, False, True])
True
>>> is_palindrome([])
True
>>> is_palindrome(["a", "l", "a", "s", "k", "a"])
False
>>> is_palindrome(["r", "a", "d", "a", "r"])
True
>>> is_palindrome(["f", "o", "o", "l", "p", "r", "o", "o", "f"])
False
>>> is_palindrome(["a", "v", "a"])
True
>>> is_palindrome(["racecar", "racecar"])
True
>>> is_palindrome(["r", "a", "c", "e", "c", "a", "r"])
True
"""
if len(lst) == 0 or len(lst) == 1:
return True
if lst[0] != lst[-1]:
return False
return is_palindrome(lst[1:-1])``````

Use OK to test your code:

``python3 ok -q is_palindrome``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``