Beginner - is my code using recursion?

Question

The function below checks whether a number is even or odd - simple. My question is regarding the call stack. To make sure I understand it.

Is the second else if statement (number<0) calling the main function isEven(number) so it runs again from top checking if number==0 and so on?
Is it recursion?

function isEven(number) {
  if (number == 0) 
    return true;
  else if (number == 1) 
    return false;
  else if (number<0) {
    number*=-1
    return isEven(number)
  }
  else 
    return isEven(number-2)
};


console.log(isEven(50));
// → true
console.log(isEven(75));
// → false
console.log(isEven(-1));
// → false

Answer 1

Is the second else if statement (number<0) calling the main function isEven(number) so it runs again from top checking if number==0 and so on?

Yes, that's right.

Is it recursion?

Yes, it is an example of how recursion works.

It's not a very good example though, as it can easily be rewritten to use a loop instead (or even just a single expression), so it doesn't show the advantages of recursion.

---

To better show how recursion works the function could split the number in half and call itself on each half:

function isEven(number) {
  if (number == 0) {
    return true;
  } else if (number == 1) {
    return false;
  } else if (number < 0) {
    return isEven(-number);
  } else {
    // split number in two halves
    var a = Math.floor(number / 2);
    var b = number - a;
    // number is even if the halves have the same status
    return isEven(a) == isEven(b);
  }
}

This will split the work in half and call itself to do the work of each half. It will turn the work into smaller and smaller parts until each part is the trivial work of determining if 0 or 1 is even.

By splitting the work in half instead of shaving off a small portion, the parts quickly get smaller. Calling isEven(10000) with this implementation will only make calls 13 levels deep, while the implemtnation in the original example would make calls 5000 levels deep.

Answer 2

Yes, works as you expect.

And yes, that is recursion. As is the one in the last else statement.

Please note that many advise to use recursion as the last statement, so you could rewrite it like that:

function isEven(number) {
  if(number < 0)
     number *= -1

  if (number == 0) 
    return true;
  else if (number == 1) 
    return false;
  else 
    return isEven(number-2)
};

Answer 3

You can see it's recursion because your function has a stop criteria (actually two of them, number==0 and number==1),and then calls itself. It's a very basic example of recursive function.

Answer 4

Is it recursion?

Yes, it is indeed.

Answer 5

The second condition is to support negative numbers. I would have put that on its own:

function isEven(number) {
  return isPositiveEven( number < 0 ? 
                         number*-1 : 
                         number ); 
};

Now isPositiveEven could look like this since we never have negative numbers:

function isPositiveEven(number) {
  if (number == 0) 
    return true;
  else if (number == 1) 
    return false;
  else
    return isEven(number-2)
}

How it works is that we know the evenness of 0 and 1 and it the number you provide is higher we know it has to be 2 or higher and can recurse with the same minus two since it will not change the odd/even property. Eg. isPositiveEven(3) will turn into isPositiveEven(1) and will hit the base case and return false. For isPositiveEven(2) it will turn into isPositiveEven(0) and will hit the base case and return true.

It's tail recursive, which means recursion is not really needed to do this. The same function written in terms of loops can look like this:

function isEven(number) {
  var n = number < 0 ? -1*number : number; // Math.abs(number)
  while( n > 1 ) {                         // n %= 2
    n -= 2;
  }
  return n == 0;
}

The while loop is actual a modulus operation and JavaScript has the operator % which works for negative numbers as well -10 % 2 === 0 thus this can be written as simple as:

function isEven(number) {
  return number % 2 === 0;
}

Answer 6

Yes, your example is recursive.

Any function that contains a reachable invocation of itself is recursive.

Recursion like this is leveraging the recursive function invocation feature of JavaScript.

Before ALGOL-60 in 1960 (although Lisp was defined around that time, its compiler came later), languages did not support convenient user-land recursion for two reasons:

First, early languages were register-based. Subroutine instructions would save the current memory location in the jump address, and then set the program counter to the next address. This was simpler than maintaining a stack, but it meant the programmer had to effectively implement their own recursion inside the language. When stack-based languages were introduced, recursion became easier.

Second, it was seen as being computationally expensive to achieve (and CPUs were pretty weedy back then).

JavaScript is an example of a stack-based language (as most (all?) modern languages are).

This means that the location in the execution of your program is defined by a stack data structure. The stack was chosen for this task because it offers the required last-in first-out (LIFO) behavior needed for nested subroutine calls.

The items on the stack are called stack frames or simply frames (sometimes they are called activation records) and they correspond to invoked subroutines in your program (the top frame being current). Each frame contains metadata associated with the subroutine call, and this varies with each language.

In JavaScript stack frames are called Execution Contexts, and the EcmaScript specification defines the metadata they contain.

In your example:

01    function isEven(number) {
02       if (number == 0) 
03         return true;
04       else if (number == 1) 
05         return false;
06       else if (number<0) {
07         number*=-1
08         return isEven(number)
09       }
10       else 
11         return isEven(number-2)
12    };
13
14    console.log(isEven(2)); // 2 chosen for simplicity.

// >> << indicates the currently executing expression.

          Expression           |      Current stack
--------------------------------------------------------
14 console.log(>>isEven(2)<<); |   [
                               |     { fn: global, arguments: [], ... }
                               |   ]
11 return >>isEven(0)<<;       |   [
                               |     { fn: isEven, arguments: [2], ... },
                               |     { fn: global, arguments: [], ... }
                               |   ]
03 >>return true<<;            |   [
                               |     { fn: isEven, arguments: [0], ... },
                               |     { fn: isEven, arguments: [2], ... },
                               |     { fn: global, arguments: [], ... }
                               |   ]
11 >>return isEven(0)<<;       |   [
                               |     { fn: isEven, arguments: [2], ... },
                               |     { fn: global, arguments: [], ... }
                               |   ]
14 >>console.log(isEven(2));<< |   [
                               |     { fn: global, arguments: [], ... }
                               |   ]
   >>end of program<<          |   [
                               |   ]