This assignment is Homework 17, and is due at classtime on Friday, April 7.

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?

Assignment

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 n^th term of the Fibonacci sequence.

   Specifically, let F₁ = 1, F₂ = 1, and F_n = F_{n – 1} + F_{n – 2} for n > 2. A call to fibonacci(n) should return the value of F_n.

   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 any 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.

Submitting your work

After you have finished your solutions, paste them into a single Python file. Make sure that Python can run your file without error! Please use comments (lines that begin with a # symbol) to clearly state the problem number for each solution in your file. Save your file and upload it to the HW17 assignment on Moodle.