Javascript Recursion Subtraction

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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;
      }

    }

Answer 4

The first subtraction of your recursion starts with the last two numbers and runs backwards:

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

Answer 5

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.

Answer 6

To elaborate on my comment…

Subtraction (unlike multiplication and addition, which explains 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 subtraction 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 subtracting except for that first call).

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

function sub(num){ return num - (num*(num-1)/2) }