How do Stack frames work for recursive functions?-CodePudding

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!

CodePudding user response：

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

Where in your second we make the recursive call to the function first & printing when the recursive function finishes its execution. That means the recursive function will print the element first. Hence, you'll see the elements 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


Explaination:
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

Explaination:
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.

CodePudding user response：

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])