CODEWITHSUNDEEP
pythonfunctionrecursion
jes516
jes516

Reputation: 552

recursive function help/explanation

Can someone explain what happens after lower is greater than upper and 0 is returned? I can not wrap my head around how the program is producing 4,7,9,10. I believe 0 is returned from the iteration of the call to ourSum() within the ourSum() function. This would set results to 1 + 0 which would equal to 1. Can someone spare a few moments to walk me through this?

def ourSum(lower, upper, margin=0):
    blanks = ' ' * margin
    print(blanks, lower, upper)
    if lower > upper:
        print(blanks, 0)
        return 0
    else:
        results = lower + ourSum(lower + 1, upper, margin + 4)
        print(blanks, results)
        return results

Results from ourSum(1,4) below:

 1 4
     2 4
         3 4
             4 4
                 5 4
                 0
             4
         7
     9
 10
10

Upvotes: 4

Views: 141

Answers (4)

Scott
Scott

Reputation: 6389

ourSum(1, 4):

  • this prints ' 1 4'
  • then checks: 1 < 4 -> False
  • so results = 1 + ourSum(2, 4, 4) this keeps happening until lower > upper, which happens at 5 > 4. But at this point we have 4 levels of recursion which still need numerical result returned:
  • ourSum(1, 4, 0), ourSum(2, 4, 4), ourSum(3, 4, 8), ourSum(4, 4, 12)

So first ourSum(5, 4, 16) returns 0 due to:

    if lower > upper:
    print(blanks, 0)
    return 0
  • ourSum(5, 4, 16) returns 0 so the previous recursion gets --> results = 4 (lower was = 4 at this point) + 0. So we print 4 with the appropriate number of 'blanks', AND we return results (which = 4)

  • The previous recursion was sitting there with:

    results = 3 + ourSum(4, 4, 12) but we just returned the result of ourSum(4, 4, 12) which was = 4.

So now:

  • results = 3 + 4 = 7. Print 7 and blanks and return results (ourSum(3, 4, 8) returns 7)

Keep doing this with results = 2 + ourSum(3, 4, 8), but this is 7 so results = 9. Print and keep going for the remaining results = 1 + ourSum(2, 4, 4) = 10 and finally, for our initial problem of ourSum(1, 4) we return results = 10.

Upvotes: 1

Steve Barnes
Steve Barnes

Reputation: 28370

Change print(blanks, lower, upper) to print('A', blanks, lower, upper) and you will see that you never return until after printing the zero value.

So all the first half printing is on the first print. You also need to remember that the values are all local so at the point when you have finally returned 0 you add one to the local lower value of 3 and so on.

Upvotes: 0

Yosh
Yosh

Reputation: 2742

Here is a rough illustration of what's happening: Let's forget about print and margin for now.

  • First we have ourSum(1,4)
    • else clause takes place : it returns 1 + ourSum(2,4)
      • Another else, ourSum(2,4) returns 2 + ourSum(3,4)
        • ourSum(3,4) returns 3 + ourSum(4,4)
          • ourSum(4,4) returns 4+ourSum(5,4)
            • Finally the if. return ourSum(5,4) returns 0.
          • so ourSum(4,4) returns 4+0 = 4
        • Now ourSum(3,4) is 3+4 = 7
      • OK, ourSum(2,4) is 2+7 = 9
    • ourSum(1,4) returns 1+9 = 10.

print and margin are used to report these situations nicely.

Upvotes: 2

maahl
maahl

Reputation: 547

This is because lower is different in every function call, and you add it to ourSum(...) every time to get results.

results = lower + ourSum(lower + 1, upper, margin + 4)

This line is executed at each function call. So your function basically computes the sum of every value lower takes, i.e. the sum of all numbers between 1 and 4.

The return value of the 5th call is 0.

In the 4th call, the value of lower is 4 (as you can see in the output of your function). Therefore the return value of the 4th call is lower + ourSum(...) = 0 + 4 = 4.

The return value of the 3rd call is then lower + ourSum(...) = 3 + 4 = 7. And so on.

Upvotes: 0

Related Questions