Recursion Explained

Question

Produce the sum of the first n values in an array.

function sum(arr, n) {
 
 if (n <= 0 ){
 return 0;
 } else { 
 return sum(arr, n-1) + arr[n-1];
 }
 }

Hello, I have this simple recursive function from freecodecamp. I understand the concept of recursion, however I can't seem to wrap my brain around why this works in this exact use case.

I am mainly struggling to understand how the count is being increased and stored to produce a final total sum, as well as why the function doesn't return 0 as the sum once it hits its breakpoint.

Any explanations are appreciated, thank you.

Also this is not for a project or anything of the sorts, just trying to understand this concept better.

• Dai: "why the function doesn't return 0 as the sum once it hits its breakpoint." - What breakpoint?
• Dai: "how the count is being increased" - the count isn't being increased, the value of n decreases with each reentrant step (aka recursive call).
• isherwood: @Dai, the function hits the first clause when n = 0. One could describe that as a break in the cycle.
• isherwood: Welcome, Griffin. Please see How to Ask and take the tour. Your question is a bit broad, as we're not a discussion forum. If you can, revise to ask something more specific about that code.
• David: This is probably a great opportunity to start using a debugger. With a debugger you can step through the code line by line as it executes, stepping into each recursive call of this function and observing how it behaves and how the values change. When you do that, can you identify a specific operation which doesn't do what you expect? What was that operation? What values were used? What was the result? What result was expected? Why?

Answer 1

Think of each recursive call as adding a frame on the stack. All the called frames have to give answer before you can compute answer for current frame.

Caller program starts:

FRAME_A
sum([5,7,10],3)
n <= 0: False
answer here = sum([5,7,10],2) + 10
 ^
 wait for this to be computed
 let's call this WAIT_A
--------
FRAME_B
sum([5,7,10],2)
n <= 0: False
answer here = sum([5,7,10],1) + 7
 ^
 wait for this to be computed
 let's call this WAIT_B
---------
FRAME_C
sum([5,7,10],1)
n <= 0: False
answer here = sum([5,7,10],0) + 5
 ^
 wait for this to be computed
 let's call this WAIT_C
---------
FRAME_D
sum([5,7,10],0)
n <= 0: True
return 0
FRAME_D is done.
(Now, we are rolling back)
WAIT_C is now 0. FRAME_C answer is 0 + 5 = 5. FRAME_C is done.
WAIT_B is now 5. FRAME_B answer is 5 + 7 = 12. FRAME_B is done.
WAIT_A is now 12. FRAME_A answer is 12 + 10 = 22. FRAME_A is done.
All frames are done. Final answer = 22.

• Griffin G: Thank you, this makes much more sense being able to see it this way. I appreciate the assistance.