# Some simple recursive functions

## So how do recursions work?

I hear so much about recursions. They're supposedly in all interview questions. So here's my attempt at trying to make them easy to understand.

A recursive function is a function that calls itself. I'll throw in a simple example. The factorial.

The factorial of 5 = 5 x 4 x 3 x 2 x 1. What is happening here:

- first, 5 is multiplied by 5-1 (in other words 4) = 20
- then, that result (20) is multiplied by 4-1 (3) = 60
- then, that result (60) is multiplied by 3-1 (2) = 120
- lastly, that result (120) is multiplied by 2-1 (1) = 120
- and it's over. We have the result.

There's a repetetive pattern here - the result is multiplied by (the number - 1) `n * (n-1)`

. That's where the recursive function comes in.

Here is what the function might look like. I put in lots of print statements so you can see what is happening at each point.

```
def factorial(n):
print "NOW: We're (back) at the beginning of the function. n = {}".format(n)
if n <= 0:
return 0
if n == 1:
print "--- HIT THE BASE CASE"
print "NOW: the return is 1."
print "--- WILL START GOING BACK UP THE LADDER"
return 1
else:
print " NOW: We're in the 'else statement'. n = {}".format(n)
result = n * factorial(n-1)
print """NOW: The interim result (the previous 'return') is {result_was} and n = {n}.
So {result_was} * {n} = {result}.""".format(result_was=result/n, n=n, result=result)
print " The NEW interim result (the current 'return') based on this recursion is: {}.".format(result)
return result
print factorial(3)
```

**So what is happening here?**

Let's look at the key line `result = n * factorial(n-1)`

. The number `n`

is being multiplied by ... the result of the same function `factorial(n-1)`

. In other words, a loop of the function calling itself.

Let's look at the construct of the rest of the function and we'll come back to that line. We start off with `if n <= 0: return 0`

. For this function, we don't want to deal with negative numbers or 0. So if the argument is 0 or less, it returns a 0 and that is the end.

Similarly, `if n == 1: return 1`

. If the argument of the function is 1, it returns a 1 and that is the end. This line also plays an important role in the overall function. Every recursive function **must have an end to the loop***, or it will go on in an infinite loop. So in this case, if the number is equal to 1, it stops the recursion with a `return 1`

and then the function finishes up the rest of its work. (*This is also referred to as the 'base case' - when a problem can be solved without further recursion.)

Now, let's go back and look at the crux of this function `result = n * factorial(n-1)`

. `n`

is to be multiplied by what? a function. (Of course, we can call functions in a function). In this case, it is calling the same function, with a different argument `n - 1`

. So `n`

will wait until it knows what it should be multiplied with; it will wait for the `return`

of that function.

Here is where it gets interesting. That function will then call itself again. `n`

waits for a `return`

. And since this is a recursion, there is also a new `n`

and that one also waits for a `return`

. And the recursive loop goes on and on - until it hits its 'base case'. And then the `return`

s are all in and the `n`

s can do their multiplication and be done with it.

In other words, **the recursive loop goes down the ladder and all the ns wait for their corresponding return - until it hits its 'base case', its absolute bottom. And then it goes back up the ladder.** The most recent

`return`

is multiplied to the lowest `n`

, the most recent `n`

. And the `return`

of that multiplication is multiplied to the next lowest `n`

. And so on until it reaches the top. And we have our final `return`

. That is the result of the function.**Let's see that in action. **

Here is the result of the above function - with all the print statements:

```
NOW: We're (back) at the beginning of the function. n = 3
NOW: We're in the 'else statement'. n = 3
NOW: We're (back) at the beginning of the function. n = 2
NOW: We're in the 'else statement'. n = 2
NOW: We're (back) at the beginning of the function. n = 1
--- HIT THE BASE CASE
NOW: the return is 1.
--- WILL START GOING BACK UP THE LADDER
NOW: The interim result (the previous 'return') is 1 and n = 2. So 1 * 2 = 2.
The NEW interim result (the current 'return') based on this recursion is: 2.
NOW: The interim result (the previous 'return') is 2 and n = 3. So 2 * 3 = 6.
The NEW interim result (the current 'return') based on this recursion is: 6.
6
```

Check out the flow of this function using pythontutor.com: Click on the forward button to see what is happening step by step.

**So what is happening here - step by step?**

Firstly, we start the function at the beginning and n = 3. Since `n`

does not meet the 'if statements', it goes to the 'else statement'. That's where it finds `result = n * factorial(n-1)`

and it calls the `factorial`

function, this time with `n-1`

as the argument, as `factorial(2)`

. And the 3 waits to find out what it will be multiplied by - what is the result of `factorial(2)`

? The loop begins.

Now the `n`

is 2. And it too wants to know what to be multiplied by and waits for the results of `factorial(1)`

.

And now finally, `n`

does equal 1. It has hit 'base case' and returns 1. The `return`

= 1. Now it goes 'back up the ladder; now the multiplication can begin!

The `n`

is then multiplied by that previous `return`

. So `n`

* `return`

= `new return`

. 2 * 1 = 2.

That result, the 2, is the new `return`

that the 3 is waiting for. So again `n`

* `return`

= `new return`

. 3 * 2 = 6.

And 6 is our final `return`

.

**This is the code without all the extras.**

```
def factorial(n):
if n <= 0:
return 0
if n == 1:
return 1
else:
return n * factorial(n-1)
print factorial(3)
```

WOW! That was long. But I hope that is clear. **In very short... The recursion goes down until it hits base case. And then goes up doing the function using the return from the previous step.**

more: http://www.python-course.eu/recursive_functions.php