1

I'm learning the fundamentals of Python right now by reading Thinking Python.

As I was reading a chapter about "fruitful" function, that is, a function that "returns" a value, I came across this problem. I can more or less figure out how the code of the factorial function works, but not exactly. I have trouble in understanding precisely the flow of a function involving self-calling or recursion. Btw, the printer statments in the code shown as below are scaffolding, a device used to track the flow of the function.

Without further ado, here is the code.

def factorial(n): space=' '*(2*n) print(space, 'factorial', n) if n==0: print(space, 'returning 1') return 1 else: recurse = factorial(n-1) result=n*recurse print(space, 'Returning', result) return result factorial(3)

The result or the output of this code is shockingly a v-shape. I, for the life of me, cannot figure out why the computer (or the compiler?) runs the program the way it does here. It seems like it firstly prints the first line and the last line, and then goes on to print the second line and the second to the last line...This is strange. You would expect that it always goes top down.

To illustrate the oddity of this issue, I hereby attach another piece of code that prints numbers as you count down. The code is similar and simpler, and you would expect it to behave similarly to the factorial function before. But it doesn't. There is no oddity in the order in which the lines of outcome are displayed or printed off. 

def f(n): print(n) if n==0: return 0 else: print(3*n) f(n-1) return

I would really appreciate it if you could help me with this!

Improve this question

2 Answers 2

Reset to default
2

What might confuse you is that the recursive call does not happen at the end of the function as it is the case with your example f(). Which means, you have code that is executed before stepping into the recursion and code that is executed after stepping out of the recursion. Let's have a look at what happens in factorial:

The recursive step
Pick any recursion step i you like, which is not a base case. And then look at what the function does, without following through with the recursion.

For your factorial function, let's take the call factorial(i), where iis different from 0. That call does three things:

  1. print 2*i spaces and "factorial i"
  2. call factorial(i-1)
  3. print 2*i spaces and "returning i"

So, the output is going to be:

(2*i spaces) factorial i # everything factorial(i-1) outputs (2*i spaces) returning i

You'll see that the output of factorial(i-1) gets sandwiched between the outputs of factorial(i). To perform the recursion, all you need to do is blow the pattern up. Let's take another step i-1 into account:

(2*i spaces) factorial i (2*(i-1) spaces) factorial i-1 # everything factorial(i-1) outputs (2*(i-1) spaces) returning i-1 (2*i spaces) returning i

So, you see that the indentation decreases with the calls since i decreases, which accounts for the v-shape.

The base case
It just prints

factorial 0 returning 1

Putting it all together
Now, you can find a verbal expression for what factorial(i) does: factorial(i) produces the v-shape output

 factorial i factorial i-1 ... factorial 0 returning 1 ... returning i-1 returning i

With it being true for the case i == 0, conclude from there that is is true for i+1 if you assume that is is correct for i using the list in the section recursive step. Done that, you can be sure that is how factorial(n) works for any n >= 0.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

An elegant solution. You must have studies CS and mathematics in college. It's very helpful that you point out the second step of what factorial (i) does is "calling the factorial (i-1)". And you phrase it as "sandwished". It's also neat that you use i instead of n to illustrate. i and n are both placeholders but I find it confusing to use n when the argument by default of factorial is n. Thank you!
1

Here's your code a bit restructured to make it easier to see:

def factorial(n): space = ' '*(2*n) print(space, 'factorial', n) result = 1 if n == 0 else n*factorial(n-1) print(space, 'Returning', result) return result

And that's the output for factorial(3) with the "V shape" you mentioned:

 factorial 3 factorial 2 factorial 1 factorial 0 Returning 1 Returning 1 Returning 2 Returning 6

It looks correct and does the job of calculating the factorial. To understand the order of prints seen here, think of the following:

  • The prints start with the call for 3, since that's your entry point
  • The indentation is then 3x2 = 6 spaces
  • Since for the calculation of factorial(3) the reuslt of factioral(2) is needed, this call comes next, with an indentation of 2x2 = 4 spaces. And so on for all further factorials. That's where the V shape of the first half of prints comes from.
  • All of these function calls are now "waiting" for a result to return, at the position of the recursive call in the code. Since only factorial(0) can deliver that return value without another recursion, it will print the first return value. With an indentation of 0.
  • With the above return value, the function call to factorial(1) can now calculate its result by multiplying the returned 1 with its own n, which gives 1. That's the next print, with an indentation of 2.
  • And so on for all the higher recursion steps, from the inside to the outside. And that's how the second half of the V shape is formed.

The vital thing to understand is that the result values of the functions (and thereby the print) can only occur at the END of the complete recursion tree that comes below it. That's why the call print factorial 3 is in the first line, while its corresponding Returning 6 print is at the last line - after the whole inner tree is finished.

Hard to say if I picked up the crunchpoint you had trouble understanding with, but I hope this somehow helps.

EDIT: infinite recursion

As an answer to your question, here's an example that shows how each recursive function call will have its own variable scope and therefore not know about the variables set in an another instance of the same function, ending up in a RecursionError when the maxiumum recursion depth of the call stack is reached.

def foo(): try: print("a = ", a) return # break out of loop except UnboundLocalError: print("no variable a. defining one now.") a = 3 foo() # try again foo()
Improve this answer

3 Comments

I have a question about your explanation of the order: if the v- shaped output is indeed linearly top down displayed, how does the computer keep track of all the values of "result"s? The value of the variable 'result' varies as the value of n, the argument of factorial function changes. Does the computer actually memories all the mappings of these values without you explicitly asking it to store the mappings in some dictionaries (any appropriate container)? This is why I find it hard to believe it's absolutely linearly top down instead of an outer-first-inner-second way.
Yes indeed, there's a separate function scope for each function being called, even if it's the same function that's calling itself recursively. That would be different of course if you explicitly declared the variable with global result, or used a member variable of global object like an imported module.
I have spent a little time reading your foo function and also tyring to learn "try" and "except" because I had never seen anything like them before. But I really don't know what it is that you try to demonstrate here. I've read something that goes like" since Python doesn't have a variable declaration like some other languages do, If there is an assignment to a variable inside a function, that variable is considered local." My guess is you were trying to say something like the quoted sentences. I appreicate your answer, but I feel it best for me to just start a new thread about local. I will.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.