CPSC 170 Prelab 6: Recursion

1. Consider method f below:

   int f(int a, int b)
   {
     int ans;
     if (a > b)
       ans = 0;
     else
       ans = a + f(a+1, b);
     return ans;
   }
   

   1. Circle the base case.
   2. Underline the recursive case.
   3. Trace the call f(4,6). Show the parameters and return values at each step.
   4. In general, what value does f(a,b) return? That is, what task does f perform?

2. The code below is supposed to do a sequential search, returning the first index of target in array a, or -1 if target does not appear in a.

   int find(int[] a, int target, int index)
   {
     int loc;
     if (a[index] == target)
       loc = index;
     else
       loc = find(a, target, index+1);
     return loc;
   }
   

   1. In what situation will this code work correctly?

   2. In what situation will this code not work correctly?

   3. Correct the problem(s).

3. Use mathematical induction to show that the following equivalence is true:

     1 + 5 + 9 + ... + 4i-3 = n(2n-1)