CS 21, Spring 2017

Recursion Practice

Write each of the following functions using recursion. Make sure you test your functions on a variety of inputs to verify that they work. For some or all of your functions, draw the stack diagram as it would look when the base case is reached in a call to the function.

Answers

factorial(n) - This function returns n!, the factorial of n. For instance, factorial(5) should return 120.
sumList(L) - This function returns the sum of L, a list of integers. Hint: when recursing on a list, we often use a list of length 0 or 1 as the base case. For the general case we often try to go from a list of length n to a list of length n-1.
maxInList(L) - This function returns the largest value in L, a list of integers.
blastoff(n) - This function simulates a countdown to a rocket blasting off. If you call blastoff(5) you should see the following output:
```
5...
4...
3...
2...
1...
BLASTOFF!!!
```
This is the first example we've seen of a recursive function called for its side effects, not for its return value. Still, you should approach this problem by looking for a base case and for how you can reduce the general problem into a smaller sub-problem.
getYNResponse() - This function should repeatedly prompt a user to enter 'y' or 'n', until they actually enter 'y' or 'n'. We have written this function before using a while loop. How can you replace the while loop with a recursive call?
countLetter(s, l) - This function counts the occurences of the character l in the string s. countLetter('abracadabra', 'a') would return 5. When recursing on a string, the base case is often the empty list, "".
reverse(s) - This function reverses a string, s. reverse('yellow') would return 'wolley'.
isPalindrome(s) - This function returns True if the string s is a palindrome (same backwards as forwards), False otherwise. isPalindrome('racecar') should return True. isPalindrome('palindrome') should return False.
isSorted(L) - Returns True if the list of ints L is in sorted order. Returns False otherwise.
recLinearSearch(x, L) - A recursive version of linear search. Should return True if x is in L, False otherwise.