How do Stack frames work for recursive functions?

Question

I have trouble understanding stack frames for recursive functions. Not sure if this is the right place to ask but I have tried finding examples and I still don't understand it. For example I have this recursive function for a list:

def printout(list):
    if len(list) > 0:
        print(list[0])
        printout(list[1:])

And list1 = [5,6,7,8,9] The printout would look something like this:

5 6 7 8 9

Then if I change the places of "print(list[0])" and "printout(list[1:])" like this:

def printout(list):
    if len(list) > 0:
        printout(list[1:])
        print(list[0])

The printout would then be the other way around:

9 8 7 6 5

Why is that and how would the Stack frames look for both functions? Thankful for any help!

stack frames work exactly the same as in non-recursive functions. — juanpa.arrivillaga, Sep 29 '21 at 10:58
May help: https://stackoverflow.com/questions/717725/understanding-recursion — kiner_shah, Sep 29 '21 at 11:05
Please don't use `list` as the name of a variable. `list` is already the name of the builtin class `list`. When you call your own variable `list`, you are shadowing the builtin class `list`, and this might have unintended consequences. Not to mention, it makes your code hard to read, because readers will expect `list` to refer to the name of the class, not to your variable. — Stef, Sep 29 '21 at 11:22

score 3 · Answer 1 · edited Sep 30 '21 at 06:08

In your first example elements are getting printed before we make the recursive call to the function. Hence you'll see the exact sequence printed.

Whereas in your second example, first we make a recursive call to the function and then print after the recursive function finishes its execution. Hence the recursive function will do its print first and the calling function will do it later. So, you see the elements getting printed in reverse order.

The below examples show how the function stack grows & statements get executed by any compiler.

Let's assign a number to each statement of the function.

Example 1:

def printout(list):
    if len(list) > 0:       # 1
        print(list[0])      # 2
        printout(list[1:])  # 3


Explanation:
printout([5, 6, 7, 8, 9])
    1. check if condition
    2. print(5)                    -> `prints 5 on the console`
    3. printout([6, 7, 8, 9])
        1. check if condition
        2. print(6)                -> `prints 6 on the console`
        3. printout([7, 8, 9])
            1. check if condition
            2. print(7)            -> `prints 7 on the console`
            3. printout([8, 9])
                1. check if condition
                2. print(8)        -> `prints 8 on the console`
                3. printout([9])
                    1. check if condition
                    2. print(9)    -> `prints 9 on the console`
                    3. printout([])
                        1. check if condition
                        return

If we look at the order of print statements from top to bottom. It prints the element in the given order.

Example 2:

def printout(list):
    if len(list) > 0:           # 1
        printout(list[1:])      # 1
        print(list[0])          # 2

Explanation:
printout([5, 6, 7, 8, 9])
    1. check if condition
    2. printout([6, 7, 8, 9])
        1. check if condition
        2. printout([7, 8, 9])
            1. check if condition
            2. printout([8, 9])
                1. check if condition
                2. printout([9])
                    1. check if condition
                    2. printout([])
                        1. check if condition
                        return
                    3. print(9)    -> `prints 9 on the console`
                3. print(8)        -> `prints 8 on the console`
            3. print(7)            -> `prints 7 on the console`
        3. print(6)                -> `prints 6 on the console`
    3. print(5)                    -> `prints 5 on the console`

If we look at the order of print statements from top to bottom. It shows why elements get printed in reverse order.

score 0 · Answer 2 · answered Sep 29 '21 at 11:31

Allow me to modify your recursive function to add lots of verbose explanation during its execution:

def printout(l, depth=0):
    print('   ' * depth, 'ENTER PRINTOUT({})'.format(l))
    if len(l) > 0:
        print(l[0])
        printout(l[1:], depth+1)
    print('   ' * depth, 'EXIT PRINTOUT({})'.format(l))

Contrast that with the reversed function:

def printout_reverse(l, depth=0):
    print('   ' * depth, 'ENTER PRINTOUT({})'.format(l))
    if len(l) > 0:
        printout_reverse(l[1:], depth+1)
        print(l[0])
    print('   ' * depth, 'EXIT PRINTOUT({})'.format(l))

Now we can have a better view of what happens:

>>> printout([5,6,7,8,9])

 ENTER PRINTOUT([5, 6, 7, 8, 9])
5
    ENTER PRINTOUT([6, 7, 8, 9])
6
       ENTER PRINTOUT([7, 8, 9])
7
          ENTER PRINTOUT([8, 9])
8
             ENTER PRINTOUT([9])
9
                ENTER PRINTOUT([])
                EXIT PRINTOUT([])
             EXIT PRINTOUT([9])
          EXIT PRINTOUT([8, 9])
       EXIT PRINTOUT([7, 8, 9])
    EXIT PRINTOUT([6, 7, 8, 9])
 EXIT PRINTOUT([5, 6, 7, 8, 9])



>>> printout_reverse([5,6,7,8,9])

 ENTER PRINTOUT([5, 6, 7, 8, 9])
    ENTER PRINTOUT([6, 7, 8, 9])
       ENTER PRINTOUT([7, 8, 9])
          ENTER PRINTOUT([8, 9])
             ENTER PRINTOUT([9])
                ENTER PRINTOUT([])
                EXIT PRINTOUT([])
9
             EXIT PRINTOUT([9])
8
          EXIT PRINTOUT([8, 9])
7
       EXIT PRINTOUT([7, 8, 9])
6
    EXIT PRINTOUT([6, 7, 8, 9])
5
 EXIT PRINTOUT([5, 6, 7, 8, 9])

How do Stack frames work for recursive functions?

2 Answers2