Recursion and return in javascript

Question

I am learning Javascript at CodeAcademy.com and I am having difficulty understanding an exercise question, although I appear to have found the correct answer.

The code is designed to help someone work out how much change they should give back when someone buys something. It takes in a number and calculates how many quarters and how many pennies they should give back.

Here is what I don't understand:

• Shouldn't the code stop running the first time it encounters line 11? If not, why not?

• If the code does stop running when it enters line 11, why am I able to place code after line 10 and it will execute three times before an answer is given? I discovered that this was the case, so it made me question my understanding of how the code was working! I added the line quarters += 1; after line 10 and it returns 6.

var change = 0;
var quarters = 0;
function howManyQuarters(howMuchMoney) {
  if (howMuchMoney < 0.25) {
    change = howMuchMoney;
    return 0;
  }
  else {
    quarters += 1;
    howManyQuarters(howMuchMoney-0.25);
    return quarters;  // << line 11
  }
}

change = 0.99;
console.log ("Pay out " + howManyQuarters(change) + " quarters");
console.log ("And you'll have " + change * 100 + " pennies left over");

howManyQuarters(.99) -> howManyQuerters(.99-.25) -> howManyQuarters(.74-.25) ... On line 10, the function calls itself but with a different, smaller value. This repeats until the condition on line 4 is true, then everything returns back up the stack. One exercise would be to trace all the way down the stack until you get to the return 0, then trace it back up. — jamesmortensen
– jamesmortensen, Commented Mar 6, 2012 at 8:05
The code will stop at line 11 as this it where the function howManyQuarters returns a value — Michael L Watson
– Michael L Watson, Commented Mar 6, 2012 at 8:08
Thanks for your answer. The thing I don't understand: if I add quarters += 1 again between line 10 and 11, it will give an answer of six. Why would it add another three quarters? I assumed it would only add another one? — inperspective
– inperspective, Commented Mar 6, 2012 at 8:09
function hmQ(hwM, change) { if (hwm < 0.25) { change[0] = hwM; return 0; } else { return hwQ(hwM - 0.25) + 1; } ? — Niklas R
– Niklas R, Commented Mar 6, 2012 at 9:29

Mutation Person · Accepted Answer · 2012-03-06 08:10:40Z

3

The code doesn't stop running first time on Line 11 because the first time it reaches line 10 it (effectively) returns to line 3.

Try to picture it this way. I've lined up the levels of recursion:

1.  (Line 15) howManyQuarters(0.99)
    2.  (Line 4) howMuchMoney is > 0.25...so else applies
    3.  (Line 10) howManyQuarters(0.74)  --> 0.74 = 0.99-0.25
        4.  (Line 4) howMuchMoney is > 0.25...so else applies
        5.  (Line 10) howManyQuarters(0.49)  --> 0.49 = 0.74-0.25
            6.  (Line 4) howMuchMoney is > 0.25...so else applies
            7.  (Line 10) howManyQuarters(0.24)  --> 0.24 = 0.49-0.25
                8. (Line 4) howMuchMoney is < 0.25...so enter main body of if clause
                9. (Line 6) return 0;
            11. (Line 11) return quarters;
        12. (Line 11) return quarters;
    13. (Line 11) return quarters;
14. (Line 11) return quarters;

answered Mar 6, 2012 at 8:10

Mutation Person

30.6k18 gold badges102 silver badges166 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

inperspective Over a year ago

Thanks for your answer. That is how I imagined it worked, but there's still one thing I don't understand. If I add quarters += 1 again between line 10 and 11, it will give an answer of six. Why would it add another three quarters? I assumed it would only add another one? This suggests that the code after line 10 is being executed three times too.

Teemu Over a year ago

@RicardoCollins That's because after executed called function, the programflow continues from the next expression after that function call. You could even switch lines 9 and 10, the result will be the same.

kinakuta · Accepted Answer · 2012-03-06 08:09:01Z

1

Not necessarily. With recursion, you're potentially calling a function multiple times, and each call needs to return before the code is done executing for the function. So if howManyQuarters gets called 3 times, it will execute the code immediately following the function call (in this case a return statement) that many times as well.

Hope that's clear.

answered Mar 6, 2012 at 8:09

kinakuta

9,0371 gold badge41 silver badges48 bronze badges

1 Comment

inperspective Over a year ago

Thanks for your answer. That helps. What terms could I search for to find out more information about this?

user447356 · Accepted Answer · 2012-03-06 08:09:01Z

This is the whole point of recursion: the function is calling itself until the stop condition is met and becomes true, then it won't call itself anymore.

In this case, yes the function will indeed stop at the return quarters; line, but at this point it already called itself in the line before.

The stop condition is making sure you won't have infinite loop - when calling the function, you give it a number - when that number is less than 0.25 the function will stop. So:

Basic examples:

If the initial number was less than 0.25 the function will run only once, returning 0.
If the initial number was between 0.25 and 0.5 the function will run twice - the self calling (recursion) will happen one time because the value is not smaller than 0.25 but the self calling pass the value minus 0.25 so now the value in the second call will already be less than 0.25 - stop condition met, all good.

The return value itself is managed by global variable declared outside the function - each time the function calls itself, it increments that variable by 1 so in the end you know how many times it was called. Now that's not very smart as you can see in this example - second call to the function with same amount of change will bring wrong result.

BenMorel · Accepted Answer · 2014-02-21 22:52:44Z

1

The function is correct. Recursion is an amazing and powerful method in computer science. A recursive function has always the same structure:

function myRecursive(nSizeData){
  if(baseCondition is TRUE){
    //compute the function with nSizeData
    //do stuff here
  }
  else{
    //call the same function with a smaller size set of data
    //this condition ensure that the baseCondition will eventually be matched
    myRecursive(mSizeData);
  }
}

There is a base condition that represent the foundation of the function: if the function input data match the baseCondition, the function can compute without calling itself. Otherwise, it calls itself passing a smaller size set of data. The computational process of a recursive function can be represented through a stack: I push into the stack each time the function is called, I pop the stack when the function returns a value. The first pop will always be the result of the baseCondition block.

Warning: if the baseCondition is never matched, a stackoverflow will eventually occur.

A classic example is the factorial function of an integer number:

function factorial(n){
  if(n==0 || n==1){
    return 1;
  }
  else{
    return factorial(n-1);
  }
}

See here for further information.

edited Feb 21, 2014 at 22:52

BenMorel

37k52 gold badges208 silver badges339 bronze badges

answered Mar 6, 2012 at 8:27

Alberto De Caro

5,2139 gold badges50 silver badges77 bronze badges

2 Comments

inperspective Over a year ago

Thanks for your answer. I think I understand what you say in your answer, but the thing I don't understand is this: if I add quarters += 1 again between line 10 and 11, it will give an answer of six. Why would it add another three quarters? I assumed it would only add another one?

montecruiseto Over a year ago

this helped me get recursion. +1

John Pick · Accepted Answer · 2012-03-06 08:11:35Z

0

Each time the function is entered, it has to eventually be exited via return. Here's a diagram:

Enter howManyQuarters.
  Enter howManyQuarters.
    Enter howManyQuarters.
      Enter howManyQuarters.
      return
    return
  return
return

answered Mar 6, 2012 at 8:11

John Pick

5,69033 silver badges31 bronze badges

Comments

YuS · Accepted Answer · 2012-03-06 08:23:04Z

0

Sorry, a little bit offtopic, but why do you need such complicated function for the simple math work? This is actually one-line function need instead (but with aggregated result).

function howMuchMoney(val) {
    return [
        Math.floor(val / 0.25),
        parseFloat((val % 0.25).toFixed(2))
    ];
}

This is it, just as simple.

http://jsfiddle.net/semencov/D8xUE/

answered Mar 6, 2012 at 8:23

YuS

2,0531 gold badge15 silver badges24 bronze badges

Comments

me_digvijay · Accepted Answer · 2012-03-06 09:25:26Z

0

Here what I can think is that the

return quarters;

statement is not been executed just after the line 10. When the control encounter the

howManyQuarters(howMuchMoney-0.25);

statement it calls itself without executing the line 11. When all the recursion are done the control comes out of each loop(recursion) and executes the line 11.

edited Mar 6, 2012 at 9:25

answered Mar 6, 2012 at 8:41

me_digvijay

5,53210 gold badges51 silver badges86 bronze badges

Collectives™ on Stack Overflow

Recursion and return in javascript

7 Answers 7

2 Comments

1 Comment

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

2 Comments

1 Comment

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related