What explicitly happens in a recursive function?

Question

I understand the concepts of recursion to a certain level but I am unable to understand all the steps that happen in a recursive call.

For example:

def fact(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact({}) = {} * fact({})'.format(n,n,n,n-1))
        return n * fact(n-1)

answer = int (input('Enter some number: '))
print(fact(answer))

>> Enter some number: 5
5 is not 0, so fact(5) = 5 * fact(4)
4 is not 0, so fact(4) = 4 * fact(3)
3 is not 0, so fact(3) = 3 * fact(2)
2 is not 0, so fact(2) = 2 * fact(1)
1 is not 0, so fact(1) = 1 * fact(0)
120

While I understand that it repeats the task until it reaches the base where n == 0, but how does Python store the previous 5 * 4 * 3 ... and calculates when based is reached, I am finding it a bit difficult to visualize the whole process.

Another example would be when say I pass an iterable.

def getSum(piece):
    if len(piece) == 0:
        return 0
    else:
        print(piece)
        return piece[0] + getSum(piece[1:]) 
print(getSum([1, 3, 4, 2, 5]))
>> 
[1, 3, 4, 2, 5]
[3, 4, 2, 5]
[4, 2, 5]
[2, 5]
[5]
15

The list seems to be reduced from each recursion to piece[n-1:] and again ultimately all the values returned are summed. Is there anywhere I can refer to on how Python explicitly manages recursion?

Answer 1

but then does Python automatically sum the amounts and does this for all cases?

Python doesn't have to do anything special here. Recursive function calls are just function calls. There is nothing magical about a function call.

All that happens is that the return value of a function call is used in a multiplication:

n * fact(n-1)

Python executed the fact(n-1) function call, the function returns, and Python completes the expression by multiplying n with the returned value.

Compare this to any other function you could call. Would n * math.sin(n-1) be easier to follow? You don't have to know what is inside of math.sin(), just that it returns a value, that then is used in a multiplication.

That that fact() function call was the exact same function here doesn't actually matter. Python doesn't care. Python specifically can't care because Python is so dynamic. From one moment to the next the name fact could be bound to something different, so Python just looks up fact in the table of names, and calls it with the result of n-1. No special consideration is made here for fact pointing to the same function as the one currently executing.

It may help with understanding to just create separate functions for each step:

def fact5(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact5({}) = {} * fact4({})'.format(n,n,n,n-1))
        return n * fact4(n-1)

def fact4(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact4({}) = {} * fact3({})'.format(n,n,n,n-1))
        return n * fact3(n-1)

def fact3(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact3({}) = {} * fact2({})'.format(n,n,n,n-1))
        return n * fact2(n-1)

def fact2(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact2({}) = {} * fact1({})'.format(n,n,n,n-1))
        return n * fact1(n-1)

def fact1(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact1({}) = {} * fact0({})'.format(n,n,n,n-1))
        return n * fact0(n-1)

def fact0(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact0({}) = {} * fact_minus1({})'.format(n,n,n,n-1))
        return n * fact_minus1(n-1)

Then call fact5(5) and get

>>> fact5(5)
5 is not 0, so fact5(5) = 5 * fact4(4)
4 is not 0, so fact4(4) = 4 * fact3(3)
3 is not 0, so fact3(3) = 3 * fact2(2)
2 is not 0, so fact2(2) = 2 * fact1(1)
1 is not 0, so fact1(1) = 1 * fact0(0)
120

Note that I didn't bother with defining a fact_minus1() function, we know it'll not be called when you start with fact5(5).

You could also add more information to your visualisation. You don't log the return values from functions, and you could add indentation to visualise how deep into the call structure you are:

def fact(n, _indent=''):
    print(f"{_indent}-> fact({n}) called")
    if n == 0:
        print(f"{_indent}<- fact({n}) returns 1")
        return 1
    else:
        print(f"{_indent}   fact({n}) calls fact({n-1}) ->")
        recursive_result = fact(n - 1, _indent+'  ')
        print(f"{_indent}   fact({n}) <- received {recursive_result}, multiplying with {n}")
        result = n * recursive_result
        print(f"{_indent}<- fact({n}) returns {result}")
        return result

which produces:

-> fact(5) called
   fact(5) calls fact(4) ->
  -> fact(4) called
     fact(4) calls fact(3) ->
    -> fact(3) called
       fact(3) calls fact(2) ->
      -> fact(2) called
         fact(2) calls fact(1) ->
        -> fact(1) called
           fact(1) calls fact(0) ->
          -> fact(0) called
          <- fact(0) returns 1
           fact(1) <- received 1, multiplying with 1
        <- fact(1) returns 1
         fact(2) <- received 1, multiplying with 2
      <- fact(2) returns 2
       fact(3) <- received 2, multiplying with 3
    <- fact(3) returns 6
     fact(4) <- received 6, multiplying with 4
  <- fact(4) returns 24
   fact(5) <- received 24, multiplying with 5
<- fact(5) returns 120
120

The indentation here shows that the functions are each separate namespaces on a stack. When one function calls another, the current function is 'paused', put on hold, the data it contains put on top of a stack until it can be resumed. Multiple function calls so all pile up until something finally starts to return results to their caller, at which point the previous function can resume where they left off, etc.

Answer 2

Recursive function is basic programming concept and is available in almost all the programming and scripting language. Recursive function is a loop which creates series of functions with yield on return. It's a like a Stack data structure Last In First Out

So, In Example 1, the stack is

1 * return fact(0)  // return to next statement in stack
2 * return fact(1)  // return to next statement in stack
3 * return fact(2)  // ....
4 * return fact(3)
5 * return fact(4)

So, at last 4 * fact(3) will return 24 which will be the return value of fact(4) and, Hence 5 * return fact(4) = 120.

Hope this helps!

Answer 3

Hopefully this illustrates it better:

You have this output:

5 is not 0, so fact(5) = 5 * fact(4)
4 is not 0, so fact(4) = 4 * fact(3)
3 is not 0, so fact(3) = 3 * fact(2)
2 is not 0, so fact(2) = 2 * fact(1)
1 is not 0, so fact(1) = 1 * fact(0)

We start with fact(5) = 5 * fact(4)

fact(4) is actually 4 * fact(3) (and so on until n==0)

If we were to actually write the entire recursion line out of fact(5) it would be:

5 * fact(4) * fact(3) * fact(2) * fact(1) * fact(0) #which is 1, base case

Which is actually...

5 * (4*fact(3)) * (3*fact(2)) * (2*fact(1)) * (1*fact(0)) # 1*fact(0) == 1*1

Which simplified is...

5 * 4 * 3 * 2 * 1 = 120

Answer 4

There's no magic. Let's step through.

def fact(n):
    if n == 0:
        return 1
    else:
        print('{} is not 0, so fact({}) = {} * fact({})'.format(n,n,n,n-1))
        return n * fact(n-1)

I assume you understand what happens for fact(0), so I won't go through it. Let's look at fact(2).

def fact(n):      # n = 2
    if n == 0:    # Skipping this case
        return 1
    else:
        # This is equivalent to return 2 * fact(1)
        return n * fact(n-1)

Now we step into fact(1):

def fact(n):      # n = 1
    if n == 0:    # Skipping this case
        return 1
    else:
        # This is equivalent to return 1 * fact(0)
        return n * fact(n-1)

Of course, fact(0) returns 1, so fact(1) returns (1 * 1) = 1. Now that we have the return value, we step back out to the last call of fact(2):

# This is equivalent to return 2 * fact(1)
return n * fact(n-1)

As we said, fact(n-1) is 1, so we are returning 2 * 1 = 2.

If you learn to use your debugger, you will be able to step through this and see explicitly what happens yourself. If you are using an IDE such as PyCharm, it will probably have a debugger built in that makes everything easy to visualize.