Trying to understand recursion in JS... check my simple code

Question

I am trying to wrap my head around recursive functions. I've tried a number of entry level exercises with no success. For example, I put this code into JS fiddle. I intended for it to take the sum of all numbers from 1 to n.

function sumAll(n) {
  if (n == 1 ) {
    return 1;
  } else if (n > 1) {
    return sumAll(n--) + n;
  }
}

console.log(sumAll(3));

feeding 3 to the function should give me '6'. I get an error, though.

What do you think `n--` does? How does that differ from `--n`, and why is it relevant? — Scott Hunter, Jan 25 '23 at 16:12
That said, IMO using `n - 1` is much clearer--zero cognitive overhead and anyone reading the code will understand exactly what's happening. — Dave Newton, Jan 25 '23 at 16:14
https://stackoverflow.com/questions/7031326/what-is-the-difference-between-prefix-and-postfix-operators — epascarello, Jan 25 '23 at 16:15
Tangential: instead of reporting "I got an error" be specific and tell **us** what the error is--it saves everyone a small bit of thought. — Dave Newton, Jan 25 '23 at 16:17
doing some reading on 'n--' vs '--n' now, thanks. Also, noted about the specific error. Thank you! — alex the listener, Jan 25 '23 at 16:25

score 4 · Accepted Answer · answered Jan 25 '23 at 16:12

4

The -- suffix operator will evaluate to the original value of n, and the subtraction from n will happen afterwards (which is also not desired as you still want to do + n). That means the recursive call gets the same value for n as the caller, and so you don't get closer to the end...

Don't use -- here, but -1:

function sumAll(n) {
  if (n == 1 ) {
    return 1;
  }
  else if (n > 1) {
    return sumAll(n-1) + n;
  }
}

console.log(sumAll(3));

answered Jan 25 '23 at 16:12

trincot

317,000
35
244
286

1

you can also remove the else if statement to make things even easier to read – This Guy Jan 25 '23 at 16:16
1

Sure, but maybe the author wanted to prevent infinite recursion when calling `sumAll(0)` or `sumAll(-1)` and have the function return `undefined` instead, which I actually think is a good idea. Even better would be to have a base case that catches all possible states where no recursion should happen, like `(!(n > 1))`. But all this distracts from the original question. – trincot Jan 25 '23 at 16:19
1

if ( n <=1 ) return n; – This Guy Jan 25 '23 at 16:25

score 1 · Answer 2 · answered Jan 26 '23 at 00:15

Perhaps you will enjoy a repeatable technique that can guide you through designing your recursive function. Let's solve sumAll using inductive reasoning -

If n is zero, return the empty sum, zero
(inductive) n is negative or positive. If n is negative, return the negative result of the subproblem sumAll(-n)
(inductive) n is positive. Return n plus the result of the subproblem sumAll(n - 1)

function sumAll(n) {
  if (n == 0)                  // 1
    return 0
  else if (n < 0)              // 2
    return -sumAll(-n)
  else
    return n + sumAll(n - 1)   // 3
}

console.log(sumAll(-10), sumAll(0), sumAll(10))
// -55 0 55

Here is sumAll written using a switch instead. It behaves identically but maybe you will find the syntax nicer to read -

function sumAll(n) {
  switch (true) {
    case n == 0:  return 0                  // 1
    case n < 0:   return -1 * sumAll(-n)    // 2 
    default:      return n + sumAll(n - 1)  // 3
  } 
}

console.log(sumAll(-10), sumAll(0), sumAll(10))
// -55 0 55

Here is sumAll again as a pure, functional expression -

const sumAll = (n = 0) =>
  n == 0                // 1
    ? 0
: n < 0                 // 2
    ? -1 * sumAll(-n)
: n + sumAll(n - 1)     // 3


console.log(sumAll(-10), sumAll(0), sumAll(10))
// -55 0 55

Trying to understand recursion in JS... check my simple code

2 Answers2