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. Computing a positive integer power of a number is easily seen as a recursive process. Consider aⁿ:
   • If n = 0, aⁿ is 1 (by definition)
   • If n > 0, aⁿ is a * a^n-1

   Fill in the code for power below to make it a recursive method to do the power computation.

   int power(int base, int exp)
   {
     int pow;
   
     // if exp is 0, set pow to 1
   
   
   
     // otherwise make recursive call and store result in variable pow
   
   
   
     // return pow
   
   }