Issues with Recursion using Python 3

Question

My question is about what python is doing while recursion works. I get the concept but it seems what's explicit in a loop is implicit in a recursive algorithm. I've seen examples where the recursion will loop through and then step back through to get the answer. Which I don't get. It's like code is happening that I didn't write.

I can't help 'seeing' the return statement return an equation instead of building an equation and returning the answer.

There are some examples of recursion that just make sense but the Fibonacci and factorial type algorithms are confusing. ( disclaimer: I don't want a lesson in fibonacci or factorials ^_^.)

def main():
    num = int(input("Please enter a non-negative integer.\n"))
    fact = factorial(num)
    print("The factorial of",num,"is",fact)

def factorial(num):
    if num == 0:
        return 1
    else:
        return num * factorial(num - 1)

main()

if we do !10 I can't help but think it should return the result of each of these equations and loop over that. I'm not sure how python is working through this in memory. Or how it knows that it needs to return the value of 10*9*8*7*6... etc

instead of returning return 10 * (10 - 1) return 9 * (9 - 1) return 8 * (8 - 1)

I know the return calls the function so it can't return anything... but what does it do with the value it already found without overwriting the variables and losing it's place?

Is it staring me right in the face or is there something I just don't know?

Answer 1

This is a tough question to answer in a fully authoritative way -- I think different people have different ways of thinking about recursion. My way of thinking about recursion is to force myself to think in a very disciplined, abstract way about what a function is. A function is just a mapping. That's simple in principle, but easy to forget in practice, especially if you're used to thinking in imperative terms -- that is, to thinking about programs as sets of instructions.

Forget about instructions for a moment, and think about the factorial function in its most abstract form:

X               Y
--------------------
0    ------>    1
1    ------>    1
2    ------>    2
3    ------>    6
4    ------>    24
5    ------>    120
6    ------>    720
...

Don't worry for now about how to calculate this. Just think about the abstract mapping. Now let's think about how to make a recursive version of this function. What do we need? Well, we need a function that creates a different mapping -- not a mapping from [1, 2, 3, ...] to factorials, but a mapping from one value of Y to the next. In other words (using lower-case now):

x               y
--------------------
1    ------>    1
1    ------>    2
2    ------>    6
6    ------>    24
24   ------>    120
120  ------>    720
720  ------>    5040
...

Now let's think about how to calculate this. Immediately a problem appears: 1 maps to 1 the first time and to 2 the second. So we know we're going to have to write a special case to differentiate those two. But for the others, this is pretty simple, right? Just multiply x by its position in the list. So this means for all those parts of the mapping, we need to know just two things: x, and its position in the list:

def factorial_recurrence(x, position):
    return x * position

Note that this function now has two arguments, so it's actually a slightly different function than the above:

x,   p               y
------------------------
1    0    ------>    1
1    1    ------>    2
2    2    ------>    6
6    3    ------>    24
24   4    ------>    120
120  5    ------>    720
720  6    ------>    5040

This shows quite clearly how we can differentiate between the two mappings from 1. Now we just have to come up with a way to get the position information. It just so happens that position is the same as the value of X. So one simple way would be to use a loop. Here we take care of X == 0 by simply setting x to 1 and starting our loop at 1 instead of 0:

def factorial(X):
    x = 1
    for position in range(1, X + 1):
        x = factorial_recurrence(x, position)
    return x

Now notice that the value of x here is being passed into factorial_recurrence, and then the result is being saved as x.

So what's really happening here is that the output of the function is being passed back into the function. Here's the big reveal:

That's recursion!

This is, in a crucial sense, already a recursive algorithm. It's just that the representation is inside-out here, and the function also incorporates position information from outside the recursive process. To see what I mean, look at this:

def even_factorial(X):
    x = 1
    for position in range(2, X + 1, 2):
        x = factorial_recurrence(factorial_recurrence(x, position - 1), position)
    return x

This gives the same result as factorial for every even value of X. (It gives the result of X - 1 for odd values of X.) And we don't have to stop there. We can do the same thing for every third value of X (breaking out the nesting for clarity):

def third_factorial(X):
    x = 1
    for position in range(3, X + 1, 3):
        x = factorial_recurrence(
                factorial_recurrence(
                    factorial_recurrence(
                        x, 
                        position - 2
                    ), 
                    position - 1
                ), 
                position
            )
    return x

Now do the same thing for every 4th, every 5th, and so on. If you continue this process, then for any given X, you'll eventually create a function that will return nothing but 1 until you pass X, and then when you pass X, you'll get the factorial of X.

At this point the trick of recursion is simply to realize that we can automate that process of turning the loop inside out by having factorial call itself. Every time factorial is called, it simply nests another factorial_recurrence call inside the last -- unless X is 0, in which case, it returns 1, terminating the sequence of nested calls.

def factorial(X):
    if X == 0:
        return 1
    else:
        return factorial_recurrence(factorial(X - 1), X)

So this is kind of a complicated way of thinking about recursion, but its value is that it shows, very clearly, the relationship between the abstraction of recursive functions and their concrete implementation in imperative code.

Answer 2

Think about it as a math problem. If you know the answer to !9, how would you calculate !10? You simply have to multiply the value of !9 by 10.

That's exactly what the recursive function is doing; it simply expresses the factorial of num as the same thing as num times the factorial of num - 1. The only number for which that doesn't work is 0, but the factorial of 0 is known, it is 1.

So, the factorial of 10 is basically:

• 10 * factorial(9) ==
• 10 * 9 * factorial(8) ==
• 10 * 9 * 8 * factorial(7) ==
• 10 * 9 * 8 * 7 * factorial(6) ==
• 10 * 9 * 8 * 7 * 6 * factorial(5) ==
• 10 * 9 * 8 * 7 * 6 * 5 * factorial(4) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * factorial(3) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * factorial(2) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * factorial(1) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * factorial(0) ==
• 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1

Note that each factorial() call gets a new set of variables. No overwriting takes place; it is a whole new, fresh call to the function. The value of num in each call is entirely independent from all the other calls to the function.

If it helps, try using a notebook to trace the function information. Write down the variables on a page, updating them as you step through the code manually. For every new function call, turn over the page and start on the next piece of paper, writing down variables there. You'd write 10 on the first, then 9 (num - 1) on the second page, etc. Returning means taking the returned value, ripping out the page from the notebook and going back a page in the notebook, to update the variables there with that return value.

Python does the exact same thing, using frame objects to track the variables. Each function call is a new frame, and frames are discarded again when a function returns. All the variables for that call are gone with the frame.

Also, Python doesn't care you are re-using the same function here. You could have created 11 separate functions, each with a separate name and a separate num name:

def factorial10(num10):
    if num10 == 0:
        return 1
    else:
        return num10 * factorial9(num10 - 1)

def factorial9(num9):
    if num9 == 0:
        return 1
    else:
        return num9 * factorial8(num9 - 1)

def factorial8(num8):
    if num8 == 0:
        return 1
    else:
        return num8 * factorial7(num8 - 1)

# ...
# etc. all the way to

def factorial0(num0):
    if num0 == 0:
        return 1
    else:
        return num0 * factorialminus1(num0 - 1)

and Python would not see any difference between those functions and the original. The exact same work would be executed, but instead of reusing the same function you are using a different function object with identical behaviour. Only the names changed.

So, recursion is just a clever way of chaining together a whole series of function calls. Those function calls are all separate, they don't care about what the local variables of the other functions are doing. Python doesn't have to 'know' anything, it just has to execute the function for you, and when it comes across another function call, execute that function call and use the return value. That that function is the same function or a different one doesn't make any difference.