# Some simple recursive functions

Wed 17 December 2014

Filed under Python

## 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 `n`s 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