Now that we know recursion is characterized by the use of a function that calls itself, let's have a look using the textbook example of the fibonacci sequence.

For the uninitiated, the fibonacci sequence goes something like this: 1, 1, 2, 3, 5, 8, 13, 21, 34. Each subsequent number is obtained by summing the previous two numbers.

A recursive algorithm to generate the nth number in the sequence would look something like this:

```
def fibonacci(n):
if n == 0:
return 1
elif n == 1:
return 1
return fibonacci(n-1) + fibonacci(n-2)
```

To wrap your head around this, let's use the call of fibonacci(4) as an example.

When you call the above function with a value of 4, the function will hit:

`return fibonacci(3) + fibonacci(2)`

We don't know the solution to either of these, so we call fibonacci(3) first:

`return fibonacci(2) + fibonacci(1)`

Again, we don't know the solution to fibonacci(2), so we call that which hits:

`return fibonacci(1) + fibonacci(0)`

Great! This is a problem small enough for us to solve so both of those calls to our function return 1. Then, we end up back at:

`return fibonacci(2) + fibonacci(1)`

Except this time, fibonacci(2) has a value of 2 so then fibonacci(1) is called. This quickly returns 1 so now we have completely resolved fibonacci(3) from the first iteration. It evaluates to 3!

Now we just have to deal with fibonacci(2). This hits:

`return fibonacci(1) + fibonacci(0)`

Which returns a value of 2. Our function terminates with a final evaluation of 2 + 3. We return the value 5.

Now wasn't that easy? No? That's fine, it still melts my brain.

Here's a summary of the functions indented by what level the calls actually occur:

```
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
= 1
fibonacci(0)
= 1
fibonacci(1)
= 1
fibonacci(2)
fibonacci(1)
= 1
fibonacci(0)
= 1
```

Fibonacci is a decent way to demonstrate recursion unfortunately, it is purely academic. It has no real world value since an iterative algorithm is much easier to read and works faster. Let's move on to some more practical examples.