### 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 an:

• If n = 0, an is 1 (by definition)
• If n > 0, an is a * an-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

}
```