## Recursion Algorithm

Let’s start with a basic example to get an idea of how a recursive function works:

```
def recursive(input):
if input <= 0:
return input
else:
output = recursive(input -1 )
return output
```

Below is the demonstration with the input=2.

## Implementation of the Fibonacci Sequence

Now, we are going to take a look at recursion with a famous example: the **Fibonacci Sequence**. The Fibonacci Sequence follows one rule: get the next number in the sequence by adding the two previous numbers. Here is an example of the sequence:

```
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]
```

We start with *(val_0 = 0)* –> *(val_1 = 0 + 1 = 1)*.

Then, we step through each value: *(val_2 = val_0 + val_1 = 0 + 1 = 1) –> *(val_3 = val_1 + val_2 = 1 + 1 = 2)*, …etc

We implemente `get_fib()`

in a recursive way:

```
def fb(position):
if position > 1:
output = fb(position-2) + fb(position-1)
return output
else:
if position == 1:
output = 1
return output
elif position == 0:
output= 0
return output
```

Actually, we can realize that for position 0 and 1, the output is actuaclly the position so:

```
def fb(position):
if position > 1:
output = fb(position-2) + fb(position-1)
return output
else:
if position == 1 or position == 0:
output = position
return position
Here is the compact version:
def fb(position):
if position == 1 or position == 0:
output = position
return position
else:
return fb(position-2) + fb(position-1)
```

**Tips**:

You may have noticed that this solution will compute the values of some inputs more than once. For example `get_fib(4)`

calls `get_fib(3)`

and `get_fib(2)`

, `get_fib(3)`

calls `get_fib(2)`

and `get_fib(1)`

etc… The number of recursive calls grows exponentially with *n*.

In practice if we were to use recursion to solve this problem we should use a **hash table** to store and fetch previously calculated results. This will increase the space needed but will drastically improve the runtime efficiency.