Understanding recursive functions calls

Question

Consider the following code:

def print_mah(n):
    if n <= 0:
        return
    else:
        print('mah') 
        print_mah(n-1) 

print_mah(3)

Here Python checks if n is less than or equal to 0, it finds that this is False so it prints 'mah' and calls the same function with n-1 until n is equal to 0, so 'mah' is printed 3 times.

But consider this manipulated code:

def print_mah(n):
    if n <= 0:
        return
    else: 
        print_mah(n-1)
        print('mah')

print_mah(3)

Python checks if n is less than or equal to 0, it finds that this is False so calls the same function again with n-1, and 'mah' is printed 3 times, too.

My question is that why 'mah' isn't printed just one time, in other words why print_mah isn't called with n=2, then Python finds that the condition is False, so it calls it with n=1, and finds the condition is False, so it calls it with n==0, and finds that the condition is True, so the function returns, and after that 'mah' is printed, only, once.

Answer 1

Both functions will print mah three times, because you are not returning anything after the recursive call. When you call the function inside itself you should handle the stopping condition (which you already did in your first if-condition), then after that it will NOT exit the program because a recursive call builds a stack of operations. After the last operation gets stopped (returns something), then it will start to compile the rest of the function below the recursive call on its way back, until the end of the function is reached.

Answer 2

To understand the different maybe this can help.

Algorithm 1

def print_n(n):
    if n <= 0:
        return
    else:
        print_n(n-1)
        print(n)

Algorithm 2

def print_n(n):
    if n <= 0:
        return
    else:
        print(n)
        print_n(n-1)

These algorithms should provide different results, maybe this is a good starting point for further research.

Some help

If you call a function (f2) inside an other function (f1) the current function (f1) will wait until the called function (f2) finished.

Some keywords for research

• function call
• stack

Answer 3

Python finds that the condition is False, so it calls it with n=1, and finds the condition is False, so it calls it with n==0, and finds that the condition is True, so the function returns

That actually is the exact execution path of the second version. Maybe you don't see, though, that when the function returns it picks back up where it left off after the recursive call returns, just like any other method call.

Therefore, when n==1 and it recurses with n==0, then it is returned and mah is printed the first time, then that returns and mah is printed when n==2, then that returns and mah is printed a third and final time.

Answer 4

My question is that why 'mah' isn't printed just one time, in other words why print_mah isn't called with n=2, then Python finds that the condition is False, so it calls it with n=1, and finds the condition is False, so it calls it with n==0, and finds that the condition is True, so the function returns, and after that 'mah' is printed, only, once.

The function only returns out of the most-inner function. The two function levels where the else condition is used will then continue execution after the call to print_mah and actually print. Here's a line-by-line walk through for print_mah(2) for brevity.

print_mah(2)
# Enter print_mah - Level 1

    if n <= 0: # n = 2
        # ...
    # False, continue to else

    else: 
        print_mah(n-1)  # n = 2
    # Enter print_mah - Level 2

        if n <= 0: # n = 1
        # ...
        # False, continue to else

        else: 
            print_mah(n-1)  # n = 1
        # Enter print_mah - Level 3

            if n <= 0: # n = 0
                return
            # Return None to print_mah - Level 2

        print('mah')
        # Function is complete, return None to print_mah - Level 1

    print('mah')
    # Function is complete, return None to the execution scope

Answer 5

Here is a "trace" of what the second program is doing:

print_mah(3) ->
  print_mah(2) ->
    print_mah(1) ->
      print_mah(0) ->
        # Does nothing, essentially.
        <-
      # print_mah(1) continues running.
      print('mah')  # The last thing that print_mah(1) does.
      <-
    # print_mah(2) continues running.
    print('mah')
    <-
  # print_mah(3) continues running.
  print('mah')
  <-

What we see here is that print('mah') occurs three times (therefore, 'mah' gets printed three times).

Answer 6

return doesn't break out of your entire call stack, just the current function call. In this case:

def print_mah(n):
  if n <= 0:
      return
  else: 
      print_mah(n-1)
      print('mah')

print_mah(3)

print_mah is called three times before returning 0. You can think about it as if they were just nested logic, like this:

def print_mah(n):
  if n <= 0:
      return
  else: 
      print_mah(n-1) # Replace this line with new call
      print('mah')

Where we just call the function again inside the else statement at the comment.

def print_mah(n):
  if n <= 0:
      #return
  else:
      n = n-1
      if n <= 0:
          #return
      else: 
          print_mah(n-1)
          print('mah')
      print('mah')

You can see that print('mah') shows up in sequence at the bottom, which, as it's written, will print sequentially as the functions backtrack out of the call stack.