diogenes diogenes - 2 months ago 10
Python Question

understanding recursive function python

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

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

Comments