Python, how an instruction can be done eventhough the recursion shouldn't allow it?-CodePudding

In this function:

def print_triangle (sideLength):
   if sideLength < 1 :
     return
   print_triangle (sideLength-1)
   print ( "[]"* sideLength)

The instruction:

print ( "[]"* sideLength)

Should never be reached, because the instruction:

print_triangle (sideLength-1)

Would be preventing it to be reached as it keeps calling the function, which would send the flow of the program again to the beginning of the function, that is to the top. Instead of allowing it to keep going below to the:

print ( "[]"* sideLength)

Hence, it will continue doing that until the variable sideLength becomes zero.

And yet the line:

print ( "[]"* sideLength)

Is reached and draws a triangle when you call it with say a 4 as a parameter... but how?

CodePudding user response：

You can imagine the recursive call "tree" as below. Each box represents an execution context of the function, so each time a new call is made a new box is depicted. The inner most box represents the case when the argument is 0, in that case the function will return, closing the inner box. But then the caller of that innermost box will be able to continue, and it will continue with the print instruction.

So here is the initial call:

print_triangle(4)

┌───────────────────────────────────────────────────────┐
│ sideLength ══ 4                                       │
│ print_triangle(3):                                    │
│    ┌──────────────────────────────────────────────┐   │
│    │ sideLength ══ 3                              │   │
│    │ print_triangle(2):                           │   │
│    │    ┌─────────────────────────────────────┐   │   │
│    │    │ sideLength ══ 2                     │   │   │
│    │    │ print_triangle(1):                  │   │   │
│    │    │    ┌────────────────────────────┐   │   │   │
│    │    │    │ sideLength ══ 1            │   │   │   │
│    │    │    │ print_triangle(0):         │   │   │   │
│    │    │    │    ┌───────────────────┐   │   │   │   │
│    │    │    │    │ sideLength ══ 0   │   │   │   │   │
│    │    │    │    │ return            │   │   │   │   │
│    │    │    │    └───────────────────┘   │   │   │   │
│    │    │    │ print("[]"*1)              │   │   │   │
│    │    │    └────────────────────────────┘   │   │   │
│    │    │ print("[]"*2)                       │   │   │
│    │    └─────────────────────────────────────┘   │   │
│    │ print("[]"*3)                                │   │
│    └──────────────────────────────────────────────┘   │
│ print("[]"*4)                                         │
└───────────────────────────────────────────────────────┘

CodePudding user response：

Well, think it through.

def print_triangle (sideLength):
   if sideLength < 1 :
     return
   print_triangle (sideLength-1)
   print ( "[]"* sideLength)
print_triangle (4)

First, it starts with 4

if 4 < 1 :
     return
print_triangle (4-1)
print ( "[]"* 4)

Now, before it prints off []*4, it then calls the function again, this time for 3:

if 3 < 1 :
     return
print_triangle (3-1)
print ( "[]"* 3)

Now, before it prints off []*3, it then calls the function again, this time for 2:

if 2 < 1 :
     return
print_triangle (2-1)
print ( "[]"* 2)

Now, before it prints off []*2, it then calls the function again, this time for 1:

if 1 < 1 :
     return
print_triangle (1-1)
print ( "[]"* 1)

Now, before it prints off []*0, it then calls the function again, this time for 0.

Now we know that since zero is less than 1, it returns to the last function, or 1.

Now we go backwards to the last function call.

print ( "[]"* 1)

Then to the one before that:

print ( "[]"* 2)

And then the one before that:

print ( "[]"* 3)

And finally your first call of the function:

print ( "[]"* 4)

CodePudding user response：

It executes after the base case is returned and the stack of function calls start to pop.

If you write it as follows, swapping the last two lines:

def print_triangle (sideLength):
   if sideLength < 1 :
     return
   print ( "[]"* sideLength)
   print_triangle (sideLength-1)

The difference will be that the printed triangle will be upside down.

CodePudding user response：

The instruction:
print ( "[]"* sideLength)
Should never be reached, because the instruction:
print_triangle (sideLength-1)
Would be preventing it to be reached as it keeps calling the function

This is incorrect. First, "it keeps calling the function" is wrong. This only calls the function once. When the function returns, it will continue to the next line.

In particular, you have

   if sideLength < 1 :
     return

So as soon as sideLength reaches 0 the function call will return.

As a more concrete example, let's look what happens when you call print_triangle(3). First, we check if sideLength < 1, which is false, so then we go to print_triangle (sideLength-1).

This is the recursive call print_triangle(2). Again, we check if sideLength < 1. Still falls, so we recurse again with print_triangle(1). if sideLength < 1 is still false, so we recurse one more time with print_triangle(0).

But now if sideLength < 1 is true, so we return. This puts us in back to the call where sideLength is 1, but after the recursive call. The next line of code to execute is print ( "[]"* sideLength), which is how it gets executed.

After the print, we return from the function again back to when sideLength is 2. So we print() again and return back to sideLength set to 3. And one more print before returning from the top-level call.

CodePudding user response：

If you don't return the value then the function will continue running it will then repeat. So moving:
return print_triangle (sideLength-1)

Before print( "[]"* sideLength). Will make print() only run once