Q:

Flow of a factorial function using recursion

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!

A:

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:

print 2*i spaces and "factorial i"
call factorial(i-1)
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.

