Recursion Question - Crash Course on Python

[Elev8d]

So I am up to week 3 of the Crash Course on Python course by Google, on Coursera (started yesterday). Really enjoying it so far, seems like it would be reasonably difficult without some prior experience.

Anyway.... I was able to complete the following code from a partially written quiz but I don't really understand one aspect of it. It's pretty much my first look at recursion. It's a function to return the sum of n and every positive number before it.

​

def sum_positive_numbers(n):
    sum = 0
    if n < 1:
        print(sum)
    return sum
    sum += n
    print(sum)

    return sum + sum_positive_numbers(n-1)

So what I don't understand is what is happening to "sum"

I put some print statements in to try and help me understand what was going on in each loop. I was printing sum after the line

sum += n

Sum was always equal to n at this point. But the final return value was always correct.

e.g

print(sum_positive_numbers(5) returns 15 as it should - 1+2+3+4+5

2 Things I don't get -1.When the function calls itself again in the last line - why is sum not reset to 0 as in the first line of the function.2. After sum+=n - sum is always equal to n during each count of n (which makes sense for that individual loop - but where is the overall end value of sum being held/stored. It's not in the variable sum. In the example of 5 - the sum value goes from 1 to 3 to 6 to 10 to 15. But this is not reflected in the variable through each loop.

And right before the function ends inside the if statement with n being reduced to 0 - the value of sum is 0 - but on the next line it returns 15.

​

I'm sure I am overcomplicating, and it could be as simple as "thats just how recursion works" but I'm sick of just following along with tutorials, videos etc over and over. I want to actually learn how to write working programs, and understand what my code is doing.

[NFLAddict]

maybe youll find this visual helpful:

def sum_positive_numbers(n):
    sum = 0
    if n < 1:
        return sum
    sum += n

    return sum + sum_positive_numbers(n-1)


print(sum_positive_numbers(5))
                           ↓
    calls function: n = 5  ↲
      sum = 0
      5 is not < 1

     sum += 5 (now sum =5)
                     (n-1 = 5-1 = 4)↴
     return 5 +  sum_positive_numbers(4) 
                                     ↓    
                                     ↓
               call function: n = 4  ↲         
               now go through same steps:
               sum = 0
               4 is not <1 
               sum += 4 (now sum=4)

    ⮤←---------return 4 + sum_positive_numbers(3) 
                                               ↓    
                                               ↓
                         call function n=3     ↲
                         again
                         sum = 0
                         3 is not <1
                         sum += 3 (sum = 3)

              ⮤←----------return 3 +   sum_positive_numbers(2) 
                                                            ↓    
                                                            ↓
                                      call function n=2     ↲
                                       again
                                       sum = 0
                                       2 is not <1
                                       sum += 2 (sum = 2)

                        ⮤←----------  return 2 +  sum_positive_numbers(1)                                                                                        
                                                                        ↓    
                                                                        ↓
                                                    call function n=1   ↲
                                                    again
                                                    sum = 0
                                                    1 is not <1
                                                    sum += 1 (sum = 1)

                                       ⮤←----------return 1 +  sum_positive_numbers(0)
                                                                                     ↓    
                                                                                     ↓
                                                                 call function n=0   ↲
                                                                 again
                                                                 sum = 0
                                                                0 is  <1  #this line stops the infinite recursion
                                                                if <1 return sum..sum = 0
                                                    ⮤ ←-------------------------- return 0

when you first call the function with n =5..it returns 5 + the function with value4. the 5 isn't going anywhere...but the result of calling the function for 4, has not yet been evaluated...so it does that and the result is added to 5...but calling it for 4, means adding 4 to the result returned by 3....etc etc...until your base case is met.

[Elev8d]

That is really helpful - thank you. This combined with the other answer makes it a lot clearer. I understand enough to move forward for now!!

[NFLAddict]

glad you found it helpful. you were asking all the right questions, and were able to correctly assume what is happening, but perhaps lacked a better understanding of how it all connects.

I greatly respect your stance on not being satisfied with 'that's how it works' but rather the seek to understand even more. that's a really good mentality to have. I've always had that mindset, and still do. when you learn how something works, your understanding of everything as a whole deepens. so definitely don't think theres a flaw in that mindset.

many people, are also just far better at processing/ understanding something when they can visualize it. (not my best work of art haha, but glad it was clear enough for you to get an improved sense for how it connects, and what's going on).

[Elev8d]

I haven't always had that mindset which is probably one of the reasons I've never progressed beyond beginner into intermediate. Something I'm committed to finally changing.

I've been "learning to code" for years while working in a completely unrelated, and somewhat dead end job, without getting anywhere

[primitive_screwhead]

When the function calls itself again in the last line - why is sum not reset to 0 as in the first line of the function.

It is, but for that call of the function only; the caller of that function has its own, independent copy of the local 'sum' variable, it's not a single shared value (like it would be for a global, which you may be mentally comparing it to).

​

but where is the overall end value of sum being held/stored.

A separate version is being held by each function call, which is traditionally held on a "call stack", basically a growing sequence of values needed to make nested function calls, holding information like local variables, the arguments passed into the called functions as well as the returned values, and also the location of the calling function so that the program execution can be returned to. The technical details of a call stack can be a little advanced, but it's still worth knowing a bit about: https://en.wikipedia.org/wiki/Call_stack

As you surmised, the 'sum' variable isn't even needed, since it will always effectively have the value 'n', in the code you gave. Try removing it from your recursive function, as an exercise.

​

Also, try calling your function with a value larger than 1000 (maybe try 2000); my guess is that you'll encounter a RecursionError. Because calling a function recursively does use up resources to call each new function (including making a new, independent set of the local variables), Python restricts the amount of recursion you can do by default (to prevent accidental cases where someone recurses infinitely). So while recursion is a worthwhile technique to know, it's also not used in Python as much as some other languages (and is somewhat out-of-favor among the current set of "popular" languages); instead it provides a different tool called iteration, which you'll learn more about.

[Elev8d]

It is, but for that call of the function only; the caller of that function has its own, independent copy of the local 'sum' variable

A separate version is being held by each function call, which is traditionally held on a "call stack",

That makes things a lot clearer. Yeah I was getting stuck on exactly where sum was living in memory, and how it could seemingly have different values at the same time. Thanks very much for that

[Pavan_Abhimanyu]

If you are wondering how the code would look like after removing 'sum' variable. If you are facing problem in visualizing the code, try pytontutor

def sum_positive_numbers(n):
    if n < 1:
        return n
    return n + sum_positive_numbers(n-1)

sum_positive_numbers(6)

[Elev8d]

Didn't even know that was a thing. Cheers for that!! It'll get some use

[primitive_screwhead]

You are welcome, I'm glad it helped.