Recursion and return in javascript - Stack Overflow

admin管理员组

文章数量:1391969

I am learning Javascript at CodeAcademy 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");

I am learning Javascript at CodeAcademy. 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");

• javascript
• recursion

Share Improve this question Follow edited Mar 6, 2012 at 8:07 Yoshi 54.7k1414 gold badges9292 silver badges107107 bronze badges asked Mar 6, 2012 at 7:57 inperspectiveinperspective 1,90411 gold badge2020 silver badges2222 bronze badges 4

• 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 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 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 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 Commented Mar 6, 2012 at 9:29

Add a ment  | 

7 Answers 7

Sorted by: Reset to default 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;

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.

This is the whole point of recursion: the function is calling itself until the stop condition is met and bees 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:

1. If the initial number was less than 0.25 the function will run only once, returning 0.
2. 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.

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

function myRecursive(nSizeData){
  if(baseCondition is TRUE){
    //pute 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 pute without calling itself. Otherwise, it calls itself passing a smaller size set of data. The putational 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.

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

Sorry, a little bit offtopic, but why do you need such plicated 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/semencov/D8xUE/

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 es out of each loop(recursion) and executes the line 11.

本文标签： Recursion and return in javascriptStack Overflow