# Tree Recursion

We've now seen what standard recursion looks like — a function that calls itself. We'll now make our lives slightly more complicated by introducing tree recursion — a function that calls itself *not once but multiple times.* 

A classic example of tree recursion is a Fibonacci Sequence. In this sequence, a given number is the sum of the previous two numbers. The sequence goes as follows:

$$
1, 1, 2, 3, 5, 8, 13, 21, 35, 56...
$$

Let's write this in code!

```python
def fib(n):
    '''
    Accepts any value greater than or equal to 1 and returns that term in the 
    fibonacci sequence.
    '''
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)
```

An important observation here: Why do we have `n==0` as a base case, even when that is not acceptable as an input. It's because while the user might never give us `n` as the value for `n`, our recursive calls might. Consider the case `fib(2)` — which makes the recursive calls `fib(1)` and `fib(0)`  — 1 + 0 — 1, as required! 

We could have written something like `n==1 or n==2` as our base case as well, but using this structure instead allows us to introduce the idea of base cases for inputs invalid for the user but valid for the recursive calls.

Regardless, something like `fib(4)` looks like the following in terms of recursive calls:

```python
= fib(4)
= fib(3) + fib(2)
= (fib(2) + fib(1)) + (fib(1) + fib(0))
= ((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))
= ((1 + 0) + 1) + (1 + 0)
= (1 + 1) + 1
= 3
```

It is easier to visualize by representing function calls as nodes in a tree:

![Recursive Tree for fib(4)](/files/xMFU5AkB1qIFNxeBPY94)

As you can see, this looks like an upside down tree (kinda... I wouldn't think too hard about it, most computer scientists don't go outside very often). The big idea here is that, at every stage, we make two recursive calls and then combine them in some way. This is tree recursion! 


---

# 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://calnotes.gitbook.io/cs61a-guidebook/structures-of-data/tree-recursion.md?ask=<question>
```

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.