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

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.