Sign up ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free.

Example 1

function x(num) {
  if (num == 0) {
   return 1;
  }
  else {
   return (num * x(num - 1));
 }
}

x(8);

8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

Result is 40320 as expected

Example 2

function x(num) {
  if (num == 0) {
   return 0;
  }
  else {
   return (num + x(num - 1));
 }
}

x(8);

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

Result is 36 as expected

Example 3

function x(num) {
  if (num == 0) {
   return 0;
  }
  else {
   return (num - x(num - 1));
 }
}

x(8);

8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0

Result is 4

Can someone explain why?

Shouldn't the answer be -20?

share|improve this question
8  
substraction (unlike multiplication and addition) is not commutative, and JavaScript evaluation is left-to-right, whereas your function effectively does it right-to-left. –  Touffy yesterday
1  
Basically a - b - c - d is not the same thing as a - (b - (c - d)) since two - signs make a +. –  Benjamin Gruenbaum 22 hours ago
    
8-7+6-5+4-3+2-1==4 –  edc65 21 hours ago
    
Your example 1 should test num for 1 to abort, otherwise the correct recursion term would be 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1. –  Paebbels 18 hours ago
    
To see the bracketing others have mentioned, trace the recursive call: x(7) = 7 - x(6), so x(8) = 8 - x(7) = 8 - (7 - x(6)); and you can keep going from there. Also, it's 'subtraction' (just one 's'). –  L Spice 17 hours ago

7 Answers 7

up vote 16 down vote accepted

The calculation with your function basically goes from right to left:

  8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0
= 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1
= 8 - 7 - 6 - 5 - 4 - 3 - 1
= 8 - 7 - 6 - 5 - 4 - 2
= 8 - 7 - 6 - 5 - 2
= 8 - 7 - 6 - 3
= 8 - 7 - 3
= 8 - 4
= 4

That’s because each time the function x is recursively called, the right-most expression is tried to be evaluated.

Effectively, the “stack” looks like this:

  8 - x(8 - 1)
= 8 - (7 - x(7 - 1))
= 8 - (7 - (6 - x(6 - 1)))
= 8 - (7 - (6 - (5 - x(5 - 1))))
= 8 - (7 - (6 - (5 - (4 - x(4 - 1)))))
= 8 - (7 - (6 - (5 - (4 - (3 - x(3 - 1))))))
= 8 - (7 - (6 - (5 - (4 - (3 - (2 - x(2 - 1)))))))
= 8 - (7 - (6 - (5 - (4 - (3 - (2 - (1 - x(1 - 1))))))))
= 8 - (7 - (6 - (5 - (4 - (3 - (2 - (1 - 0)))))))
= 8 - (7 - (6 - (5 - (4 - (3 - (2 - 1))))))
= 8 - (7 - (6 - (5 - (4 - (3 - 1)))))
= 8 - (7 - (6 - (5 - (4 - 2))))
= 8 - (7 - (6 - (5 - 2)))
= 8 - (7 - (6 - 3))
= 8 - (7 - 3)
= 8 - 4
= 4

JavaScript’s evaluation for a “pure” subtraction is:

8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0; // -20
share|improve this answer
    
It's worth mentioning that there's nothing inherently 'pure' about your last expression 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0. In fact, this operation is mathematically meaningless; one has to specify a convention, which JavaScript does by insisting that subtraction associates left to right: see precedence level 13 of developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… , and compare to exponentiation at precedence level 14, which associates right to left, so that 8^7^6^5^4^3^2^1^0 means the unimagineably huge 8^(7^(6^(5^(4^(3^(2^(1^0))))))). –  L Spice 17 hours ago
    
@LSpice mathematics is convention. There's no natural meaning in a sequence of numbers and dashes, but it certainly has meaning in mathematics. And JavaScript semantics agree with mathematics in the case of those operators, so, inasmuch as mathematical notation is part of our symbolic culture, that expression, if not "pure" (and I agree that's not an applicable word), at least has (a single, unambiguous) meaning. –  Touffy 8 hours ago
    
@Touffy, agreed that, not mathematics, but the interpretation of a string of symbols as mathematics, is convention. I think that, outside of a grade-school setting where the teacher has made up a convention (or a programming setting, where the programmer has had to memorise the language's convention!), most people wouldn't know what to do with an expression like 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0. I'm a professional mathematician, and I know that I'd refuse to try to compute it without first asking for some parentheses, or an explicit agreement on their implicit placement. –  L Spice 4 hours ago
    
Schechter's list of common math errors points out a peril of assuming that everyone reads expressions the same way: TI-85 and TI-89 calculators give different answers for 2^3^4, because of different associativity conventions (math.vanderbilt.edu/~schectex/commerrs/#Fractions)! –  L Spice 4 hours ago

Because your function is effectively computing this right to left:

8 - (7 - (6 - (5 - (4 - (3 - (2 - (1 - 0))))))) => 4

And not:

8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0 => -20
share|improve this answer

The first substraction at your recursistion starts with the last two numbers and running backwarts:

x = 8-7-6-5-4-3-2-(1-0)
x = 8-7-6-5-4-3-(2-1)
x = 8-7-6-5-4-(3-1)
x = 8-7-6-5-(4-2)
x = 8-7-6-(5-2)
x = 8-7-(6-3)
x = 8-(7-3)
x = (8-4)
x = 4
share|improve this answer

The equation 8-7-6-5-4-3-2-1-0 written with recursion needs to have something to repeat. 8 is not part of it because it does not subtract it. So you should do something like:

= 8 + ( "recursion starting from 7")
= 8 + ( -7 + "recursion starting from 6")
...
= 8 + ( -7 + -6 + -5 + -4 + -3 + -2 + "recursion starting from 1")
= 8 + ( -7 + -6 + -5 + -4 + -3 + -2 + -1 + "recursion starting from 0")
= 8 + ( -7 + -6 + -5 + -4 + -3 + -2 + -1 + -0 /* end case */ )

The code would be something like

   function x(num, first){
      if (first){
        return num + x(num-1, false);
      } else if (num > 0){
        return -num + x (num-1, false);
      } else {
        return 0;
      }

    }
share|improve this answer

As others answered, the subtraction is being done sort of backwards, from right to left:

x = 8-7-6-5-4-3-2-(1-0)
x = 8-7-6-5-4-3-(2-1)
x = 8-7-6-5-4-(3-1)
x = 8-7-6-5-(4-2)
x = 8-7-6-(5-2)
x = 8-7-(6-3)
x = 8-(7-3)
x = (8-4)
x = 4

What you're looking for, is an inverse of the addition, which could be written as follows:

function addition(num) {
    if (num == 0) {
        return 0;
    }
    else {
        return (num + addition(num - 1));
    }
}

function subtraction(num) {
    return num - addition(num - 1);
}

Calling subtraction(8) would yield -20, because it is subtracting the sum of all of the lesser numbers, whereas your original function subtracted all of the lesser numbers from each other.

share|improve this answer

To elaborate on my comment…

Substraction (unlike multiplication and addition, which explain why your other examples work) is not commutative, and JavaScript evaluation is left-to-right, whereas your function effectively does it right-to-left.

To get the correct result with your existing code, you can use the fact that a substraction is an addition of a negative number. In the chain, only the left-most number is positive. Re-using your sum function:

function sub(num) {
    return num - sum(num - 1)
}

A purely recursive, single-function solution would require an extra argument either to know where to stop (starting from zero), or to make a special case for the first call (adding instead of substracting except for that first call).

Of course, if you don't mind cheating with arithmetics, you can linearize to

function sub(num){ return num - (num*(num-1)/2) }
share|improve this answer
    
I don't think that it's relevant to say that JavaScript evaluation is left-to-right. Even if JavaScript evaluated calls left-to-right (I don't know the actual order), the code given would still, correctly, yield 4—because of the structure of the call tree (as in @Xufox's answer stackoverflow.com/a/32999383/390158 ), not order of evaluation. –  L Spice 14 hours ago
    
If JavaScript evaluated right-to-left, the expression 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0 would evaluate to -4. Which would contradict convention, but not the result from OP's function. The evaluation tree is a direct consequence of the evaluation order. –  Touffy 9 hours ago
    
The evaluation of the expression 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0 is controlled by associativity, not order of evaluation; by associating left-to-right, it becomes (((((((8 - 7) - 6) - 5) - 4) - 3) - 2) - 1) - 0, which is unambiguous. (Compare an (illegal) expression like i + i++, whose result really is controlled by order of evaluation.) However, that is not what @Syahrul typed; the actual code expands to 8 - (7 - (6 - (5 - (4 - (3 - (2 - (1 - 0))))))), which, because of the parentheses, is unambiguous, again regardless of order of evaluation. –  L Spice 4 hours ago

Why not -20 and subtraction is not beginning from 8? because function is looping trough all those numbers, after reaching 0 Function beginning subtraction. But before all function making x(num - 1) operation. You could simply figure it out from 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 that function is multiplying first 2 * 1 = 2 and then 2 * 3 = 6 then 6 * 4 ...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.