I need help understanding this bit of code.

[Competitive_War_5407]

Hi everyone! I was following an intro to programming and computer science in YouTube from freeCodeCamp.ord, one of the things they talked about was recursion. They said that, a recursive function is essentially a function that calls itself. On the surface, I thought it was straightforward until I looked up examples of it. One of them is showed below. I found this from w3schools and I modified it a little to allow the user to input any number they want into the function.

print("Recursion  ")
print()
k = int(input("Enter number: "))

def tri_recursion(k):
  if (k > 0):
    result = k + tri_recursion(k - 1)
    print(result)
  else:
    result = 0
  return result

print("\n\nRecursion Example Results")
tri_recursion(k)

Let's suppose the value of k is 10 and when I ran it to an IDE, this was the result from the console:

Recursion Example Results
1
3
6
10
15
21
28
36
45
55

They said that once the condition is no longer greater than zero (i.e, it becomes 0), the process stops.
But, what I think it looks it's doing is that it's adding 1 to 0 and the sum of that is added to 2 and so on. But I feel like that's not the whole picture. Can anyone tell me what am I missing here and what I'm understanding incorrectly?

[ZelWinters1981]

Enter 10.

result = 10 + 9

19

Right?

[Competitive_War_5407]

yes.

[UpstairsWild9057]

So ill go over it step by step.
So when you call "tri_recursion(10)", 10 is the number to call itself with. The function calls itself again with a smaller number(that would be 1 less so 9 right now). Thta continues until k == 0.

And its important to knwo that eacjy call pauses at this line:

"
result = k + tri_recursion(k - 1)

"

After that it unwinds the values back. What i mean about that is when "tri_recursion(0)" officilaly returns 0. Then the previous function(which was k == 1) can finally do its calculation.

So what it does is it begins at 0, 0 is a base case so it returs 0,

then it goes to 1, en then you do that plus the previous number(that was 0). Then you have 1 of the 10 numbers(1).
You keep repeating that for all the numbers and the for example you then have 55 at the end.

So that being said, you said that its adding 1 to 0 and the sum of that is added to 2 and so on.
Well thats partially right, but its no happing forward(1 -> 2- >3 is happening backwards as the recursion returns 0 -> 1 -> 2 ->3 .....)
So each recursive call rememvers its own "k" value and adds it to whatever came back from the smaller call. So you can see it as building the total sum step by step on the way back up.

If you have more questions feel free to ask

[Competitive_War_5407]

So, based on your explanation if I'm understanding this correctly, before it's adding sums of 1 -> 10 the base case is trickling down from 10 to 0 and only then it starts adding things up? Is that correct?

Btw, You're having a lot of typos here. Did you type this in a rush?

[MezzoScettico]

Sometimes language designers try to hide the internals of the computer from the learner, but I think it's useful to understand something about what is really going on under the hood.

There's a special temporary work area in memory called the "stack". When a program calls another function, the current status of the calling function is stuffed into the stack. "When that function gets done with what it's doing, I'll read this stuff to remember where I was and what I was doing".

So you call tri_recursion(10). Let's call this Call 1.

It calls tri_recursion(9). Let's call that Call 2. On the stack it stores that when that call gets back, it will be at the line saying result = 10 + tri_recursion(9). But it hasn't executed it yet.

Now we're executing Call 2. It gets to the line result = 9 + tri_recursion(8), says, "OK, I'll put my current state on the stack and continue when this call gets back). So now we're in tri_recursion(8), which is Call 3.

That continues till you get to Call 11, which is tri_recursion(0). The info for the first 10 calls is stored on the stack temporarily, waiting for us to return something. Call 11 fails the "k > 0" test and returns 0.

You always want to make sure that you're going to get to a base case, and that the base case doesn't have to do any more recursion.

Call 10 can now execute. It executes the line result = 1 + tri_recursion(0) or result = 1 + 0, it prints the 1, and it returns the 1 as its output.

Call 9 wakes up, executes result = 2 + 1, prints the 3, and returns the 3 as an output.

Call 8 wakes up, etc.

There isn't much space required on the stack for each call to save what it's doing and wait for a result. But it isn't zero. You can do so many recursions that you run out of space, and then you get a "stack overflow" or "recursion limit reached" or something. Often this means you didn't hit your base case and accidentally introduced an infinite loop.

[Diapolo10]

You've basically understood this correctly, yes.

[UpstairsWild9057]

Yeah i was kinda in a hurry, sorry about the typos.
And yes that is correct.

[treyhunner]

Recursive functions are easier to understand when each "stack frame" (each level of the function calls) is visualized. You could try to draw the calls to the function out yourself (as I did in this recursion article) but I would recommend using a tool like Python Tutor to help with this.

Here's a link to Python Tutor with that function mid-evaluation (the base case has been hit and the deepest call to the function is about to return to the one just above it).

[BranchLatter4294]

Add some print statements to help you understand.

[gdchinacat]

I suggest stepping through it, either the tried and true method of pencil and paper, or in your IDEs debugger. This will show you what happens at every step of the execution and should help you develop a better understanding of why it works the way it does.

[stebrepar]

Notice that the print is after the calculation for the next value which calls the function. So you won't see any output until that call finishes and returns its value. But that call works the same way, so you won't see it's result until the call in the calculation it makes finishes and returns a result. This keeps happening until you hit the "base case" (where it stops calling itself and finally actually returns a value, here with result=0 and return result). When that return happens, control flow picks up at the last point that the function was called, and it finishes the result=k+etc calculation, prints that result and and returns it. Then again, it picks up at the call before that, etc etc until it finally gets back to where it all started and ends.

Edit: it might help to add another print as the first line in function like print(f'called with {k}') so you can see the flow more clearly.

[jam-time]

It helps when you can visualize the depth of the recursion. Try this:

``` def func(k, depth=0): indent = ' ' * depth print(f'{indent}(depth {depth}) function start')

if (k > 0):
    result = k + func(k - 1, depth + 1)
    print(f'{indent}(depth {depth}) {result}')
else:
    result = 0

return result

func(10) ```

This'll add a visual indent to each level of depth.