Understanding Recursion Challenge

JavaScript
1

I’m currently in the Basic JavaScript section replace-loops-using-recursion and I don’t quite get the way in which the code works.

I have read the superb article on recursion found under “Get Help” → “Watch a Video” (theres no video) and understand the principle of recursion, and how it works, but don’t get how the code works.

Here is the code I have come up with, which works, but I don’t get how it works.

   function sum(arr, n) {
     if (n <= 0) {return 0;}
     else {
       //console.log(sum(arr, n - 1) + arr[n]);
       return sum(arr, n - 1) + arr[n - 1];
       }
   }
 
 console.log("\n" + sum([1,2,3,4,5,6],3));

Here is as far as I get it.

  1. function sum is called with an array and a single digit number passed into the function
  2. I don’t get exactly how the below line works. Can someone spell it out for me.
    I get what return does but what does sum(arr, n - 1) do and what does arr[n - 1]; do
 return sum(arr, n - 1) + arr[n - 1];

  **Your browser information:**

User Agent is: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/88.0.4324.96 Safari/537.36.

Challenge: Replace Loops using Recursion

Link to the challenge:

2

Ok. I worked it out. This part
sum(arr, n - 1)
just calls the array again with a new lower number decremented by 1
This part
+ arr[n - 1]
will keep the running total for each call until decrementation reaches the base case, ie 0
if (n <= 0) {return 0;}

At the bottom of thois post I have included a small table of two columns that returns the correct results for each value of n, using the function given in the above post (the OP).

Here it is worked through for the case of n=1, n=2, n=3 and n=4.

Hope this helps :slight_smile:

Case n=0.

  • this is the base case
if (n <= 0) {return 0;}

Total = 0.

Case n=1.

  • calls function, adds array element 0 which is 1, then decrements to 0
  • calls function, then exits becasue the base case has been reached.
    Total = 1.

Case n=2.

  • calls function, adds array element 1 which is 2, then decrements to 1. Total = 2
  • calls function, adds array element 0 which is 1, then decrements to 0. Total = 2 + 1
  • calls function, then exits becasue the base case has been reached.
    Total = 3.

Case n=3.

  • calls function, adds array element 2 which is 3, then decrements to 2. Total = 3
  • calls function, adds array element 1 which is 2, then decrements to 1. Total = 3 + 2
  • calls function, adds array element 0 which is 1, then decrements to 0. Total = 3 + 2 +1
  • calls function, then exits becasue the base case has been reached.
    Total = 6.

Case n=4
…
Total = 10

n total
0 0
1 1
2 3
3 6
4 10
5 15
6 21

3

What is not clear to me is how or where the running total is held.

Does someone know where or how this is held.

There appears to be no variable assigned to holding this.

4

Well, the function returns the value
sum (arr, n-1) + arr[n-1]
Let’s take the example from above.
The function returns this:

let n=3
let arr=[1,2,3,4,5,6]


sum(arr, n-1) + arr[n-1]  
= sum(arr, n-1) + 3 
= sum(arr, n-1-1) + 2 + 3 
= sum(arr, n-2) + 5 
= sum(arr, n-3) + 1 + 5 
= 0 + 1 + 5 = 6

Hope this makes it clear, but if you have any questions, please do ask

Edit:
As far as storing the total goes:
In this specific case, the return statement is equivalent to “return 6”.

1 Like
5

Hi,

There is no need to declare a variable that hold the result. When the function is called from an other function it returns the value to that function that can use it.
But you also can declare a variable that hold the total as follows but the result is the same:

function sum(arr, n) {

    let result;

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

I hope I have understood your question!

3 Likes
6

@moriel
@michaelmanke00
thanks, that’s clear.

The replace-loops-using-recursion challenge description and example needs an over haul with clearer specific information as outlined in these posts.

The problem, in my opinion, was that there isn’t enough information to get your head around recursion becasue the challenge introduction missed out information that could have been there.

The challenge needs an update as follows. Add:

  1. "return" acts as a variable holding the result as the function repeatedly re-calls itself. A variable is not necessary becasue return acts in this capacity.
  2. "return" acts as a variable that can add (++) or subtract (–) from itself, without var++ or var-- being specifically used.
  3. Worked through example solution as both you and I have spelled out.
7

This is not really true. A return statement is not really a variable. The return statement just says what to do with a value.

Again, not really true. The return statement does not act like a variable. A return statement ends the function call and returns the value in that line to the calling context. There is no variable binding unless the calling context saves that return value into a variable.

Recursion is hard. The description is accurate, but it is completely normal to struggle with recursion. This exercise really brings to light any misunderstandings a person may have about functions, function calls, function scope, and return values.

2 Likes
8

Think of it this way. If instead of calling itself, what if it called a different function?

return differentSum(arr, n - 1) + arr[n - 1];

The return merely waits for the expression

differentSum(arr, n - 1) + arr[n - 1]

to “return” a value and then return returns that value.

The only difference here is that it is calling itself. But it is still just waiting for the expression to return a value.

3 Likes
9

Or perharps an even easier example:

return (8-6)*9

I think it’s really intuitive, that this returns 18 and not (8-6)*9 and in the same way, the above function simply returns the value that you get from what comes afterwards

2 Likes
10

Exactly. A return statement executes the computation on that line and returns the value back to the place in the code where the function was called.

It is important to know that a variable binding is not automatically created. If you want to use the result from a function call (the returned value) more than once, then you need to bind that value to a variable yourself.

1 Like
11

@JeremyLT

That is a lot clearer.

So return just shuttles a value around, even if it does not hold it as a kind of variable.

As someone who has not come across the recursion problem before, or not at least for a long time , the key concept that stopped me getting to grips with this challenge was not recursion of itself, but the method by which the number was held and

  • added to,
  • subtracted from or
  • multiplied by
    etc.

I did not realise what was holding my understanding back, until I realised that return was acting as a kind of variable of sorts. At least my thinking about it that way really helped my conceptual understanding of what was going on.
When I thought of it that way I got the conceptual breakthrough I needed.

You have made clear that return is not a variable.

But thinking of it as a psuedo variable makes it possible to make the leap in understanding to knowing what is happening. That is what happened for me.

Until this challenge people are used to seeing changing values stored in variables.
This is the first example in the course where this does not happen.
Some small level of explanation is necessary.

Why? Becasue the student realises - eventually - that the value has to be held somewhere … but there is no variable. So thinking of it in pseudo variable terms helps. Helps a lot.

Possibly offer the following explanation in the challenge:
“think of return in this case as acting kind of like a pseudo variable, then once you’ve got this idea please realise that it isn’t. Actually the return statement ends the function call and returns the value of the calling context back into the function.”

12

This is what I meant by understanding function calls and return statements.

I really think this is not a good idea. This can lead to some serious misunderstandings. Calling a return statement a pesudovariable isn’t accurate, and it masks the fact that a return value must be stored in a variable if you want to reference it later.

1 Like
13

perhaps this simple clarification could help:

Think of it like this:

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

Thank you everyone for your helpful comments.

They certianly made a difference to me.

Here are some thoughts I have on developing the idea of explaining how return works in the context of recursion in this challenge: replace-loops-using-recussion.

In my opinion a slightly fuller explanation of the return mechanism within the code is necessary becasue this is the first example in the course where values are “passed around a function” without using a variable.

I think some thought needs to be given to this aspect of explaining the challenge.

Sometimes, in any area of life, we have to use initial explanations that “let us into an idea”, that let us “understamd an idea”, even if the initial explanation of an idea is not strictly correct. Any initial idea should work as a spring board to a full understanding, not as the full understanding.

Learning this way often allows a student to comprehend a bigger picture such that they can make the step towards a correct understanding of a bigger concept.

When such an initial understanding is offered a caveat should be given as follows “it’s not the correct understanding” but the “correct understanding is coming.”

Then once the teacher has the class on board with the concepts a further development of the idea is given that rounds thing out.

I feel this is a better approach than trying to take a class from 0 to 100%, or zero to hero, and loosing half the class on the way.

Often teachers forget what they already know, in other words what they already know is so obvious to them that they forget, or do not realise, that there is a “sticking” idea or concept, that they have passed over, that is holding their student class up, that needs some level of explanation.

We have all listened to someone making an explanation, and said to ourselves while listening to them doing so:

“that person does not realise that while they understand the concept inside out they are assuming that everyone else does so as well, and they are missing or taking forgranted some key concepts / steps, becasue those concepts/ steps are second nature to them”

Often teachers make the mistake of not allowing pupils to “find their feet” through concepts.

BTW Free Code Academy is a fantastic platform. The above is intended as helpful criticism so that others can grasp the concept a little more easily.

15

I see what you are saying, but I firmly disagree with teaching this particular misunderstanding. Teaching wrong information about return statements can make it harder to understand when you need to store the returned value in a variable.

It is much more accurate and clear to say ‘the code on the line with the return statement is evaluated and the resulting value is returned to the place in the code where the function was called.’

The idea of doing a computation in a return statement was introduced here:

1 Like
16

Slowing down and using building blocks in comprehension is a widley accepted technique.

I feel that some how, by what ever means, a small explanation of the number being stored, where ever it is stored, as it is added up, is necessary.

Given my comprehension sticking experience with this non-variable counter, I feel a small amount more, in explanation, would provide a practical means by which students can make the transition to where we all want them to be, which is a full understanding.

Yes, I did that challenge, and I don’t think it covers the understanding of return as used in this challenge.

17

I am aware that it is a teaching technique, and it’s one I use. I object to teaching this particular piece of wrong information as a building block. Many learners struggle to properly use return values from function calls because they seem to have some impression that the result is automatically stored somewhere for them. This misleading language would reinforce this misunderstanding.

1 Like
18

I think I get the concept now, or at least get what I didn’t understand now, so any or no change of explanation in the challenge won’t affect me.

I’m just wandering though whether some small modification of the explination, that tells something about their being a counter in action somewhere, would help others, who come after me?

(Remember my sticking point was I could not see a variable, so I couldn’t see how there could be a counter. It was a proper brick wall for me)

19

I worry, and I think JeremyLT does too, that, at the risk of sounding too harsh, thinking of return as a pseudo variable will at best provide a short term illusion of understanding and simply put off the confusion into the future.

I will summarize the basic idea again, starting from scratch, because it really isn’t that much.

function sum(arr, n) {
     if (n <= 0) {return 0;}
     else {
       let result = sum(arr, n - 1) + arr[n - 1]
       return result
       }
   }
 
 console.log("\n" + sum([1,2,3,4,5,6],3));

We have two variables, namely ‘arr’ and ‘n’.
In our case arr=[1,2,3,4,5,6] and n=3

We have a function that returns a result. In our case the result is 6.

That’s it.

The confusion only comes from the recursion, but it really isn’t necessary.
A function is basically something that takes input and gives output. Our output is a value. Just like for example 4 is a value. So you can think of a function that gets passed input as nothing else than a value.

I assume you wouldn’t have an issue accepting, that 4 doesn’t need to be declared as a variable in this case:

function returnFour(){
    return 4
}

// and btw: console.log(returnFour() == 4)  <== this will log 'true' to the console.

So just as you don’t need to assign 4 to a variable to return it, you also don’t need to assign 6 to a variable. However you can, to make life easier (as I did above).

And in our case we are simply returning the result. And the result is 6.
Simply ignore the concept of backtracking as something new. It is nothing else than a different way to write a value. In our case that value is 6.

2 Likes
20

There really is no counter in this challenge :confused:
Edit: The only thing that could be considered a counter is ‘n’, which is a variable

1 Like