> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/15.-asymptotics-ii/15.2-recursion.md).

# 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. 

{% embed url="<https://youtu.be/Ht6ySSoC0FM>" %}

Consider the recursive function `f3` below:

```java
public static int f3(int n) {
   if (n <= 1) 
      return 1;
   return f3(n-1) + f3(n-1);
}
```

#### What does this function do?

Let's think of an example of calling `f3(4)`:

* The first call will return  `f3(4-1) + f3(4-1)`&#x20;
* 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 :

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FS35bGr6MiaNCfbwHM90x%2Fimage.png?alt=media&amp;token=ce4b3450-369a-4c5e-b7aa-913ec081648b" alt=""><figcaption><p>Visualization of f3's recursive calls</p></figcaption></figure>

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.

### Method 1: Intuition

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:

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2F888CQe1RDaq5NifxR1OL%2Fimage.png?alt=media&amp;token=df69fec4-da44-40d8-9563-1410bb9ca2ce" alt=""><figcaption></figcaption></figure>

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$$.

### Method 2: Algebra

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.&#x20;

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:&#x20;

$$
C(N)=1+2+4+...+2^{N-1}
$$

Applying the formula we saw earlier for the sum of the first powers of 2:&#x20;

$$
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)$$.

### Method 3: Recurrence Relation (Out of Scope)

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)$$.