javascriptrecursion

How do increment and decrement work with recursion


I can't understand how increment works with recursion.So if i have returned value which require calling the function before adding specific value.

let x = 0;

function func(n) {
  if (n > 0) {
    x++;
    return func(n - 1) + x;
  }
  return 0;
}

console.log(func(5));

why the output is not 15.

func(5) = func(4) + 1
func(4) = func(3) + 2
func(4) = func(2) + 3
func(2) = func(1) + 4
func(1) = func(0) + 5
func(0) = 0

then after unwind it the result is 15 not 25 as it has compiled.


Solution

  • This isn't what's happening:

    func(5) = func(4) + 1
    func(4) = func(3) + 2
    func(3) = func(2) + 3
    func(2) = func(1) + 4
    func(1) = func(0) + 5
    func(0) = 0
    

    This is:

    func(5) = func(4) + 5
    func(4) = func(3) + 5
    func(3) = func(2) + 5
    func(2) = func(1) + 5
    func(1) = func(0) + 5
    func(0) = 0
    

    Because x is used after the recursion unwinds:

    return func(n - 1) + x;
    

    So none of these addition operations happen until after x has been incremented 5 times.

    Swap the operands:

    return x + func(n - 1);
    

    Then the value of x used in that expression will be evaluated before entering the recursion which further increments x. For example:

    let x = 0;
    
    function func(n) {
      if (n > 0) {
        x++;
        return x + func(n - 1);
      }
      return 0;
    }
    
    console.log(func(5));