diogenes - 1 year ago 44

Python Question

I am trying to understand what happens when this recursive function is called. The code is supposed to be a trace

`def mysum(lower, upper, margin):`

blanks = ' ' * margin

print blanks, lower, upper

if lower > upper:

print blanks, 0

return 0

else:

result = lower + mysum(lower + 1, upper, margin + 4)

print blanks, result, lower, margin

return result

if __name__ == "__main__":

mysum(1, 4, 0)

the output reads

`1 4`

2 4

3 4

4 4

5 4

0

4 4 12

7 3 8

9 2 4

10 1 0

I don't understand why the function begins to unwind after it returns 0. Can you help me follow through what happens

Answer Source

Here is the code with comments helping you to begin to understand how the recursive function works.

```
def mysum(lower, upper, margin):
blanks = ' ' * margin # First time : margin = 0
# 2nd time : margin = 4
print blanks, lower, upper # first time : lower = 1, upper = 4
# 2nd time : lower = 2, upper = 4
if lower > upper: # first time : go to else (& 2nd time, ... until lower =5)
print blanks, 0
return 0
else:
result = lower + mysum(lower + 1, upper, margin + 4) # result is not directly calulated
# first it need to execute the call to
# the function, it will be the second call
print blanks, result, lower, margin
return result
if __name__ == "__main__":
mysum(1, 4, 0) # First call of your function
```

When lower is at 5, there is no call to mysum and it returns 0. So you unwind just one step : lower is at 4, and you where in the "else" part. You have to finish it

```
result = lower + mysum(lower + 1, upper, margin + 4)
print blanks, result, lower, margin
return result
```

with lower = 4 and the last call returned 0. The result = 4. And you unwind another step : lower is at 3, and the call just before returned a 4, so the new result is 7. This value is returned.

Now, lower = 3, you do the same, for lower = 2, lower = 1.

You can see that 1 + 2 + 3 + 4 = 10. And it is the result of your function. I hope that I helped you, tell me if you don't understand, maybe can I find another way to explain ... :/