Get count of odd numbers in a given integer recursively

Question

Good day, I am trying to get the number of odd numbers in a given integer, say 15 should return 7, 3 should return 1, etc... Now i was able to do that simply in a for loop, but I want to achieve it recursively now. This is my code:

var count = 0;
function oddCount(n){ 
    if(n !== 0 && !isNaN()) {
        return count;
        if(n%2 === 0) {
            count ++;  
            return oddCount(n-1); 
        } else {
            return oddCount(n-1); 
        }
    }
} // oddCount();

console.log(oddCount(14));

The console always returns an undefined value. Thank you for any support in advance. :)

*"3 should return 1"* It should? I take it 3 doesn't *contain* 3 then? — T.J. Crowder, Jan 18 '18 at 18:39
*"Now i was able to do that simply in a for loop, but I want to achieve it recursively now."* There's an even simpler way: `Math.floor(n / 2)`. — T.J. Crowder, Jan 18 '18 at 18:39
Two typo-style errors jump out: 1. `!isNaN()` will always be `false`, because you haven't passed anything into `isNaN`, so it will check `undefined`, which coerces to `NaN` and thus `isNaN` will return `true` -- and then the `!` inverts it to `false`. 2. `if (n%2 === 0)` checks for an **even** number, not an odd one. Voting to close as typo/non-repro/not-useful-to-others-in-future. — T.J. Crowder, Jan 18 '18 at 18:42
You said you wnated odd count but `if(n%2 === 0)` gives you even count — Huangism, Jan 18 '18 at 18:42
@T.J.Crowder Well you just helped me by pointing out the `!isNaN()` function, i removed it, returned count, and everything is working fine now. — BeedZ Sh., Jan 18 '18 at 18:46
@BeedZSh.: I thought that might help! But there was an aspect of this specific to recursion (I take it you're doing this for practice/to learn), so I posted an answer. :-) — T.J. Crowder, Jan 18 '18 at 18:55

score 3 · Accepted Answer · answered Jan 18 '18 at 18:53

As I mentioned in the comments, there's a typo in that you're not passing anything into isNaN.

But looking at the recursion aspect: With a recursive function, you almost never want it to operate on something it closes over (count in your case). You want it to be pure.

So instead, keep everything local within the function (or passed in as a parameter). You can think of recursive functions as being a bit like state machines: Each call just needs to work out the answer for its single input, but then aggregate that with the result of the recursion (aggregate = add in this case). See comments (obviously, this is verbose for the purposes of explanation):

function oddCount(n){ 
    // Zero => zero, NaN => NaN
    if (n === 0 || isNaN(n)) {
       return n;
    }
    // n % 2 is 0 for evens, 1 for odds.
    // Count the value for the one *below* the one passed in (since when
    // checking 3 we only want to check 0, 1, and 2, e.g., not the 3 as
    // well).
    // Then simply add in the result of the recursive call:
    --n;
    return n % 2 + oddCount(n);
} // oddCount();

console.log(oddCount(0));  // 0
console.log(oddCount(1));  // 0
console.log(oddCount(2));  // 1 (1)
console.log(oddCount(3));  // 1 (1)
console.log(oddCount(4));  // 2 (1 and 3)
console.log(oddCount(14)); // 7 (1, 3, 5, 7, 9, 11, and 13)

Thank you so much, this is exactly what I wanted. 1 thing tho is that I didnt really understand what happened in `n%2 + oddCount(n)`. — BeedZ Sh., Jan 18 '18 at 18:59
And Im getting **Maximum call stack size exceeded** error when i input large numbers — BeedZ Sh., Jan 18 '18 at 19:02
@BeedZSh.: That's the nature of recursion, you only get to go so many levels before you run out of stack (unless tail-call optimization can be done -- which it could here, but most JavaScript engines still don't support it [and some may never do so]). — T.J. Crowder, Jan 18 '18 at 19:10
@BeedZSh. About `n % 2 + oddCount(n)`: As I said in the comments above it, `n % 2` will be 0 for an even number or 1 for an odd number. Then we take that value (0 or 1) and add the result of calling `oddCount` recursively for the next value, and that lets us add up the total. — T.J. Crowder, Jan 18 '18 at 19:11

score 1 · Answer 2 · answered Jan 18 '18 at 18:51

You don't need to track the count externally, instead, try to increment the value that's returned from your function. Also, as others have pointed out, the increment needs to happen when n % 2 is not 0, e.g. :

function oddCount(n){ 
  if (n === 0) return 0;
  return n % 2 === 0 ? oddCount(n - 1) : oddCount(n - 1) + 1;
}

score 0 · Answer 3 · answered Jan 18 '18 at 18:51

You have your odd comparison wrong, also your isNaN condition will always evaluate true

var count = 0;

function oddCount(n) {
  if (n == 0 || isNaN(n)) {
    return count;
  } else {
    if (n % 2 === 0) { // If n%2 is 0 then n is even.
      return oddCount(n - 1);
    }
    count++;
    return oddCount(n - 1);
  }
}

console.log("Number of ODD numbers: " + oddCount(15));

Mulan · Answer 4 · 2018-01-18T20:44:21.370

And Im getting Maximum call stack size exceeded error when i input large numbers

TJ's answer is great, per usual. I'll include this answer because it addresses the stack-overflow issue. Below, we look at a simplified implementation of oddCount.

const oddCount = n =>
  n === 0
    ? 0
    : (n % 2) + oddCount (n - 1)
    
console.log (oddCount (0))  // 0
console.log (oddCount (1))  // 1
console.log (oddCount (2))  // 1
console.log (oddCount (3))  // 2
console.log (oddCount (4))  // 2
console.log (oddCount (5))  // 3
console.log (oddCount (15)) // 8

// i can't do it, captain!
console.log (oddCount (100000)) // RangeError: Maximum call stack size exceeded

To fix this, we have to move the recursive call into tail position; meaning all other evaluation of the function is complete and making the recursive call is the last thing your function does...

We can do this in a variety of ways, but one versatile technique involves simply adding a state parameter (or more, if needed) to your function. Here, we add acc which represents an accumulated sum of the odd numbers and set the default value to 0.

const oddCount = (n, acc = 0) =>
  n === 0
    ? acc
    : oddCount (n - 1, acc + (n % 2))
    
console.log (oddCount (0))  // 0
console.log (oddCount (1))  // 1
console.log (oddCount (2))  // 1
console.log (oddCount (3))  // 2
console.log (oddCount (4))  // 2
console.log (oddCount (5))  // 3
console.log (oddCount (15)) // 8

// but still broken???
console.log (oddCount (100000)) // RangeError: Maximum call stack size exceeded

Most importantly, notice the position of oddCount now – all of the arguments to oddCount can be completely evaluated and only thing left to do is recur oddCount – we have achieved a tail-recursive form!

// ...
: oddCount (n - 1, acc + (n % 2))

In a language that supports tail-call elimination, that's as far as you'd need to go to avoid your stack error. As of today however, JavaScript has no such optimisation. ES6 standard included support for tail-call elimination, but somewhere along the lines it became politics and the optimisation seems to be stuck in feature limbo for the time being.

No problem though. JavaScript already supports infinite looping with while, so we can invent our own mechanism to write stack-safe recursive functions even in a language that doesn't have tail call elimination. Cool!

const recur = (...values) =>
  ({ tag : recur, values : values })
   
const loop = f =>
{
  let acc = f ()
  while (acc && acc.tag === recur)
    acc = f (...acc.values)
  return acc
}

const oddCount = n =>
  loop ((m = n, acc = 0) =>
    m === 0
      ? acc
      : recur (m - 1, acc + (m % 2)))
    
// now it works for huge numbers
console.log (oddCount (10000000)) // 5000000

Get count of odd numbers in a given integer recursively

4 Answers4