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 returns are all in and the ns 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


Comments


DeeKras.com © Dee Kras Powered by Pelican and Twitter Bootstrap. Icons by Font Awesome and Font Awesome More