Recursion question

Hi Everyone,

I used Python Tutor to look at code from one of the challenges. I’ve read a lot about recursion over the past few hours and watched some videos, but I’m still missing something, at least, with this specific code. None of the resources I’ve reviewed cover an example like this one that has a setup like sum(arr, n). They seem to always have just one value.

I actually solved this one quickly on the second try, but it was kind of a fluke so I want to make sure I understand it better.

Below you can see that I’m at step 13 of 13. I’ve got two questions:

  1. Why does 5 not get added to the 9?

  2. What is the purpose of " + arr[n - 1]" in the return? It seems as thought the 9 is calculated by the function and never impacted by the second half of the return (+ arr[n - 1])

Thanks!

Instead of the current return statement, try putting the sum call in a variable by itself and then printing it out.
Then add the arr[n-1] and print again.
Then return the variable.

The print outs should show you why you need the second half of the statement.

Hello @fullyard.

Because you called sum([2,3,4,5],3) where:

  • arr = [2,3,4,5]
  • n = 3

n-1 is used as an index:

  • arr[n-1] => arr[2] // 4
  • arr[n-1] => arr[1] // 3
  • arr[n-1] => arr[0] // 2

Without + arr[n - 1] the function returns 0.
This code is using a stack, IMO you should research how an stack works.

Have you watched this video? https://youtu.be/_NsEWXD4lJ8

Cheers and happy coding

Thanks @hbar1st and @Diego_Perez. I appreciate the time you took to provide the information. The video that @Diego_Perez shared confirmed my understanding of how everything works. I kind of figured out a little more after posting.

That said, while I understand how everything works to get the calculations with this, the return equation’s “visuals” throws me off a bit. In the example below from one of the videos I watched, there’s a clear value on each side of the * for each pass through. It’s visually clear that something is getting multiplied by something on the way back up.

With the code from the freeCodeCamp challenge, there’s an n-1 on both sides of the equation and since we’re not adding the same value with itself each pass through on the way up, I have trouble visualizing in my mind what it would look like drawn out.

At the end of the day it’s not important. I just add up the right side and I get the correct answer. One of my personal flaws is that I tend to want to understand things at a micro level. This causes problems for me when learning languages (speaking) as well. I’ll just need to do what I do when learning languages. After racking my brain with no obvious answer as to why something’s conjugated a certain way I just tell myself that it’s not important why, it’s only important that I understand what it means and how to use it :slight_smile:

Keep in mind what n means and the fact that array are 0 indexed.

The nth entry of arr is at arr[n - 1]. The sum of the first n - 1 entries therefore is actually

for (i = 0; i < n - 1; i++) sum += arr[i];

where the values of i go up to n - 2!

Try the logging method I mentioned.
Or just grab a piece of paper and work out how the function is executing line by line.

I can start you off, but this is very laborious so I hope you can do it yourself.
First give each line a number.

01 function sum(arr, n) {
02
03   if (n <= 0) {
04      return 0;
05   } else {
06      let result = sum(arr, n - 1);
07      console.log("result is " + result);
08      result += arr(n-1);
09      console.log("add arr(n-1) to get " + result);
10      return result;
11    }
12 }
13 
14 sum([2,3,4,5], 3);

(I added the console logs I’ve been telling you to add and split up the code into multiple lines so you can see it do its thing)

Execution Trace:
Run line 14: call sum([2,3,4,5], 3)
Run line 01: sum begins with arr=[2,3,4,5] and n=3
Run line 03: is 3 <= 0? no.
Run line 05: else
Run line 06: result = call sum(arr, 2) then wait 
|--> Run line 01:  sum begins with arr=[2,3,4,5] and n=2
     Run line 03: is 2 <= 0? no
     Run line 05: else
     Run line 06: result = call sum(arr, 1) then wait
     |--> Run line 01: sum begins with arr=[2,3,4,5] and n=1
          Run line 03: is 1 <= 0? no
          Run line 05: else
          Run line 06: result = call sum(arr, 0) then wait
          |--> Run line 01: sum begins with arr=[2,3,4,5] and n=0
               Run line 03: is 0 <= 0? yes
               Run line 04: return 0
          <--|
          Run line 07: log "result is 0"
          Run line 08: result = 0 + arr[0] = 2
          Run line 09: log "add arr(n-1) to get 2"
          Run line 10: return 2
      <--|

Oh, that is very good to know! I knew array’s were 0 indexed but I had no idea that n meant the nth entry. I just assumed it was a randomly selected letter. I must have overlooked that somewhere in the training. Thanks for the heads up!

There is a lot of text in this challenge, but its in the spec:

Write a recursive function, sum(arr, n), that returns the sum of the first n elements of an array arr.

I really appreciate it, thank you! I think my brain is fried for the day but I’ll definitely go over this tomorrow.

Hey @hbar1st I think I finished it correctly but just want to make sure. Does this look about right?

Execution Trace:
Run line 14: call sum([2,3,4,5], 3)
Run line 01: sum begins with arr=[2,3,4,5] and n=3
Run line 03: is 3 <= 0? no.
Run line 05: else
Run line 06: result = call sum(arr, 2) then wait 
|--> Run line 01:  sum begins with arr=[2,3,4,5] and n=2
     Run line 03: is 2 <= 0? no
     Run line 05: else
     Run line 06: result = call sum(arr, 1) then wait
     |--> Run line 01: sum begins with arr=[2,3,4,5] and n=1
          Run line 03: is 1 <= 0? no
          Run line 05: else
          Run line 06: result = call sum(arr, 0) then wait
          |--> Run line 01: sum begins with arr=[2,3,4,5] and n=0
               Run line 03: is 0 <= 0? yes
               Run line 04: return 0
          <--|
          Run line 07: log "result is 0"
          Run line 08: result = 0 + arr[0] = 2
          Run line 09: log "add arr(n-1) to get 2"
          Run line 10: return 2
     <--|
     Run line 07: log "result is 2"
     Run line 08: result = 2 + arr[1] = 5
     Run line 09: log "add arr(n-1) to get 5"
     Run line 10: return 5 
<--|
Run line 07: log "result is 5"   Run line 08: result = 5 + arr[2] = 9
Run line 09: log "add arr(n-1) to get 9"
Run line 10: return 9
<--|
Run line 07: log "result is 9"
1 Like

All correct except for the last line.

This will not happen.

Instead the sum will exit out to line 14 at this point.
(Your indentation was off so I fixed it)

That’s great, thank you again for this and the time you took to do it. Very helpful and much appreciated!

1 Like

Np. Try to work out the execution on paper the next time it stumps you. It is easier to see things that way.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.