# Analysis of a Recursive Function

Performing an analysis of a recursive function is not all that different from performing an analysis of a non-recursive function. We are still going to use the same methodology to find a formula that will represent the number of operations required for a given data size. We will then use that formula to find a curve that best describes the resource usage growth rate.

## Analysis of Factorial function

How would we perform an analysis on the following piece of code?

```cpp
unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;              //base case result
    if(n > 1)                 //if n > 1 we  have the recursive case
        rc= n * factorial(n-1);  //rc is n * (n-1)!
    }
    return rc;
}
```

Start by declaring our mathematical variables and functions

Let $$n$$ represent the number we are finding the factorial of

Let $$T(n)$$ represent the number of operations it takes to find n! using our recursive function

Similar to iterative version of our code, we will simply count our operations:

```cpp
unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;        // 1
    if(n > 1)                    // 1

        rc= n * factorial(n-1);  // 3 + number of ops done by factorial(n-1)

                                 // There are 3 operators, but it also
                                 // calls factorial(n-1) so we must count
                                 // not just 3, but also all ops done by 
                                 //factorial(n-1)
    }
    return rc;                    //1
}
```

Now\... by definition $$T(n)$$ represents the number of ops needed to our function (factorial) requires when given $$n$$as its argument. But this also means that $$T(n-1)$$ would represent the number of ops needed by our function to find (n-1)! (ie number of operations performed by our function when n-1 is passed in as the argument.

Thus, we can actually rewrite our count summary as follows:

```cpp
unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;        // 1
    if(n > 1)                    // 1

        rc= n * factorial(n-1);  // 3 + T(n-1)
    }
    return rc;                    //1
}
```

Now\... how do we solve this though? So, lets start by looking at our base cases. If n <= 1, we do exactly 3 operations:

```
unsigned int rc = 1 ;
n > 1
return rc;
```

In otherwords, we can say the following:

$$T(0) = 3 \ T(1)=3$$

Remember that $$T$$is a function that represents how many operations our function requires to find factorial of the argument n. So if argument was 0, it takes 3 ops, if argument was 1, it takes 3 ops also. Notice how the analysis of this coincides with the base case of the recursive function

For n >= 2, we do the following 6 operations + we need count number of ops in the recursive call:

```
unsigned int rc = 1 ;   <--- 1 op
n > 1                   <--- 1 op
return rc;              <--- 1 op
rc= n * factorial(n-1)  <--- 3 operations, =, * and - ... also need to count
                             number of ops done by factorial(n-1)
```

Thus, we can write the expression as following for the general $$T(n)$$for n >=2

$$T(n) = 6 + T(n-1)$$

Now\... by definition T(n) represents the number of ops needed to find n! using our function. But this also means that T(n-1) would represent the number of ops needed to find (n-1) factorial using our function. Thus,

$$T(n) = 6 + T(n-1)$$

by the same token, we can say that

$$T(n-1) = 6 + T(n-2) \ T(n-2) = 6 + T(n-3)$$

etc...

In other words T(n-1) = 6 + number of operations done by factorial(n-2). Similarly T(n-2) = 6 + number of operations done by factorial(n-3)

The above statement is true for all values of n >= 2. However, we also know that:

$$T(1) = 3$$ and $$T(0) = 3$$

Thus, what we have is:

$$\begin{align\*} T(n) &= 6 + T(n-1) \ &= 6 + 6 + T(n-2) \ &= 6 + 6 + 6+T(n-3) \ ... \ T(n) &= 6 + 6 + 6 + .... 6+ 3 \end{align\*}$$

There are a total of (n-1) 6's.We know this because we need to reach T(1) to get the 3.

Thus:

$$T(n) = 6(n-1) + 3 = 6n-3$$

Thus, $$T(n)$$ is $$O(n)$$