Matthew L. Wright
Assistant Professor, St. Olaf College

# Homework 16: Recursion

## CS 121 ⋅ Spring 2016

The following exercises involve recursion. Before you write any code, think about each problem and answer the following:

• What will be the base case in your recursive algorithm?
• How can you reduce the problem to toward the base case by a recursive function call?

1. Write a recursive function called revList() that reverses a list.

Your function should take a list as its argument, and it should return a new list containing the same elements as the original list, but in the reverse order.

For example, revList(['a', 2, True]) should return [True, 2, 'a'].

This is Exercise 2 in the Recursion Exercises of the online Python text.

2. A palindrome is a word or phrase that read the same forward and backwards, such as "racecar". Write a recursive function called isPalindrome() that determines whether or not a string is a palindrome.

For example, isPalindrome('racecar') should return True, while isPalindrome('computer') should return False.

3. The Fibonacci sequence is the sequence of numbers 1, 1, 2, 3, 5, 8, 13, …. The first two numbers of the sequence are each 1; otherwise, each number is the sum of the preceeding two.

Write a recursive function, fibonacci(n), that computes the nth term of the Fibonacci sequence.

Specifically, let F1 = 1, F2 = 1, and Fn = Fn – 1 + Fn – 2 for n > 2. A call to fibonacci(n) should return the value of Fn.

For example, fibonacci(4) should return 3, and fibonacci(15) should return 610.

This is Exercise 5 in the Recursion Exercises of the online Python text.

4. Modify the recursive tree program to produce a more realistic tree. Specifically, implement three of the following ideas:

• Modify the thickness of the branches so that as branchLen gets smaller, the line gets thinner.
• Modify the color of the branches so that as branchLen gets very short, the branch is colored like a leaf.
• Modify the angle used in turning the turtle so that at each branch point the angle is selected at random in some range. For example, choose the angle between 15 and 45 degrees. Play around to see what looks good.
• Modify branchLen recursively so that instead of always subtracting the same amount you subtract a random amount in some range.

This is Exercise 3 in the Recursion Exercises of the online Python text.