# Solving Recurrence Relations
### By: Caitlin McCarthy & Katie Leger

Good news! The analysis of the recursive algorithm is very similar to that of the iterative algorithm! We are going to show you how to solve recurrence relations step by step.

## Let's try an example!
Consider this javascript function for solving the power of a number.

// returns the fibonacci number at the index represented by num
function power(num, exp) {
    if(exp === 0) {
        return 1;
    } else {
        return num * power(num, exp - 1);
    }
}

#### 1. Decide on a parameter
The main parameter of this function is the exponent, because that number will be the one changing every time the function is called.

#### 2. Identify the algorithm's basic operation
The basic operation of this function is

return num * power(num, exp - 1);

because the multiplication is the main operation of the function and will be calculated exp times.

#### 3. Check whether or not the amount of times the basic operation executes differs with inputs of the same size
The function will always be executed the same amount of times with the same input.

#### 4. Set up the recurrence relation
We see that there is one base case:

if(exp === 0) {
    return 1;
}

- Therefore, the two base cases are F(1) = 1 and F(0) = 0

Now for the recurrence:

- We know the basic operation, and from that we can conclude the recurrence relation is `F(n) = F(n-1) + F(n-2)`
- We set up the equation
`F(n) = c + F(n-1)` for n > 1 and c is a constant representing num
` = 1` for n = 0

#### 5. LAST STEP! Solve the recurrence relation
We are going to use the method of plugging in small numbers to find the pattern of the recurrence relation.

We are going to use c = 2 and taking it to the 4th power.
`F(1) = c + F(0)` --> 2
`F(2) = c + F(1)` --> 4
`F(3) = c + F(2)` --> 8
`F(4) = c + F(3)` --> 16
The pattern here is 2ⁿ, therefore the runtime would also be 2<sup>n.