CSE 131 / 501N (Summer 2014) Recitation Questions

Because this module concerns recursion, your answers to the problems below must involve recursive solutions. No credit will be given for non-recursive answers.
1. For each of the following functions, write a Java method that computes the function's values.
• f(x) = 2 * f(x-1) + 7, if x > 0; otherwise f(x) = 0
• f(String s, int n) = n + f(s,n-1), if n > 0, otherwise f(s,n)="" (quote-quote, the empty string)
• f(int n) = f(n-5), if n ≥ 5; f(4) = false; f(3) = false; f(2) = false; f(1) = false; f(0) = true
• binom(n,k) = (binom(n-1,k) + binom(n-1,k-1)) / 2.0, if n > 0 and k ≥ 0 otherwise binom(n,k) = 1.0
2. For each of the following, identify the substructure and write a recursive method to compute the function.
• f(x,n) = x0/0! + x1/1! + ... + xn/n!
Recall that n! means the factorial of n, so you can make use of a separate (recursive) factorial function.
• f(x, n) = 1/x + 2/x2 + ... + n/xn
• f(n) = n - ((n-1) - ((n-2) - ... - 0))
• f(n) = 0 - 1 - 2 - ... - (n-1) - n
3. For any of the above, be able to apply the subsitution model for reasonably small values of input parameters.
4. For any of the above, be able to identify the base case, and be able to state the values for which your method is valid.
5. Sedgewick 2.3.32 on page 285 (it's what you did for lab)