# 15.2 Recursion

Here we go again...

Now that we've done a couple of nested for loops, let's take a look at our favorite problem: recursion.

Consider the recursive function

`f3`

below:public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

Let's think of an example of calling

`f3(4)`

:- The first call will return
`f3(4-1) + f3(4-1)`

- Each
`f3(3-1)`

call will branch out to`f3(2-1) + f3(2-1)`

- Then for each
`f3(2-1)`

call, the condition`if (n <= 1)`

will be true, which will return 1. - What we observe at the end is that 1 will be returned 8 times, meaning we have
`f3(2-1)`

summed 8 times. - Therefore,
`f3(4)`

will return 8.

We can visualize this as a tree, where each level represents a recursive call and each node value represents the argument to the function :

Visualization of f3's recursive calls

You can do a couple more examples, and see that this function returns

$2^N-1$

. Visualizing the recursive calls is extremely useful for getting a sense of what the function is doing, and we will discuss a few methods of determining runtime in recursive functions.Based on the visualization below, we can notice that every time we add one to

`n`

we double the amount of work that has to be done:Then, adding one to

`n`

N times means doubling the amount of work N times, which results in the intuitive answer for runtime to be $2^N$

.Another way to approach this problem is to count the number of calls to

`f3`

involved. Utilizing the same tree visualization above, we can see that the number of calls to f3 at each recursive level is equivalent to *the number of nodes at each recursive level**of the tree. For instance, the number of calls we made to*`f3 `

at the top level is 1, at the second level is 2, at the third level is 4, etc. The total number of calls to f3 then is the

**sum**of the number of nodes at each recursive level, which can be expressed as the equation below:$C(N)=1+2+4+...+2^{N-1}$

Applying the formula we saw earlier for the sum of the first powers of 2:

$1+2+4+8+...+Q=2Q−1$

Substituting

$Q$

with $2^{N-1}$

, we get:$C(N)=2Q−1=2(2^{N-1})-1=2^N-1
$

The work during

*each call*is constant , so the overall runtime for`f3`

is $\theta(2^N)$

.This method is not required reading and is outside of the course scope, but worth mentioning for interest's sake.

We can use a "recurrence relation" to count the number of calls, instead of an algebraic approach. This looks like:

$C(1)=1 C(N) = 2C(N-1) + 1$

Expanding this out with a method we will not go over but you can read about in the slides or online, we reach a similar sum to the one above. We can then again reduce it to

$2^N - 1$

, reaching the same result of $\theta(2^N)$

.Last modified 1yr ago