# 15.2 Recursion Now that we've done a couple of nested for loops, let's take a look at our favorite problem: recursion. {% embed url="" %} 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)` * 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 :

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:

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. 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)$$. ### 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)$$. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://cs61b-2.gitbook.io/cs61b-textbook/15.-asymptotics-ii/15.2-recursion.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.