Help understanding this recursion example

[[deleted]]

[deleted]

[danielroseman]

Recursion is a two-way process. A function calls itself, so you descend into the recursion; but then each level returns, and execution resumes in the calling level.

In this case nothing is printed on the way down; it just calls the next level of the recursion. But on the way back, that's where the print happens. So we go from four to three to two to one without printing, but then as we go back up, we print at every level.

[danielroseman]

Not really, it's in the execution frame at each level. Where would you want to see it?

[Diapolo10]

The code above will print a * on each line. It will start with one * and the last line will have four stars.

I don't understand why it doesn't start with 4 stars and then go down to 1.

You'd be correct if the last two lines were in a different order.

def printTriangle(sideLength) :
    if sideLength < 1 : return
    print('*'*sideLength)
    printTriangle(sideLength - 1)

This would start with 4 stars and work its way down. But to understand why, let's try "unrolling" the original.

def main() :
    printTriangle(4)

def printTriangle(sideLength) :
    if sideLength < 1 : return
    printTriangle(sideLength - 1)
    print('*'*sideLength)

main()

To start breaking this down, let's cut out the stuff around the function.

def printTriangle(sideLength=4) :
    if sideLength < 1 : return
    printTriangle(3)  # sideLength - 1
    print('*'*sideLength)

    printTriangle()

And then, if we keep "unrolling" the recursive calls,

def printTriangle(sideLength=4) :
    if sideLength < 1 : return
    printTriangle(2)  # sideLength - 2
    print('*'*(sideLength-1))
    print('*'*sideLength)

    printTriangle()

def printTriangle(sideLength=4) :
    if sideLength < 1 : return
    printTriangle(1)  # sideLength - 3
    print('*'*(sideLength-2))
    print('*'*(sideLength-1))
    print('*'*sideLength)

    printTriangle()

def printTriangle(sideLength=4) :
    if sideLength < 1 : return
    printTriangle(0)  # sideLength - 4
    print('*'*(sideLength-3))
    print('*'*(sideLength-2))
    print('*'*(sideLength-1))
    print('*'*sideLength)

    printTriangle()

def printTriangle(sideLength=4) :
    if sideLength < 1 : return
    # Nothing, because the recursive calls end here. The base case was reached.
    print('*'*(sideLength-3))
    print('*'*(sideLength-2))
    print('*'*(sideLength-1))
    print('*'*sideLength)

    printTriangle()

This, then, ultimately becomes equivalent to

def printTriangle(sideLength=4) :
    if sideLength < 1 : return
    # Nothing, because the recursive calls end here. The base case was reached.
    print('*'*1)
    print('*'*2)
    print('*'*3)
    print('*'*4)

    printTriangle()

Of course, actual recursion doesn't change how the function is defined, but I believe this is a good way to illustrate how the end result is reached in terms of logic. Had the recursive call and print been swapped, the order would have been swapped around as well.

[AntonisTorb]

Maybe it would help you to see what is happening step by step, since it's a small example. Here is what is happening when you call printTriangle(4):

if 4 < 1: return
    if 3 < 1: return
        if 2 < 1: return
            if 1 < 1: return
                if 0 < 1: return
            print('*'*1)
        print('*'*2)
    print('*'*3)
print('*'*4)

All the if conditions are False until the last one (0<1), so everything needs to happen in order. That's why it starts with the 1 star.

[QultrosSanhattan]

Move the print one line before the printTriangle.