Checking for evenness through recursion (Eloquent javascript-exercise)

Question

I've started reading Eloquent Javascript, and there's an exercise about making a recursive function to check for evenness. I've made it in a couple different ways, it's quite simple, but for some reason I can't get it to work with negative numbers anymore. I had it working, then probably accidentally changed something, and now it only works for positives.

Could you please tell me why this code is 'wrong'?

(textfield.append just prints something to a textfield I've made in an html/css-document, so I can save the exercises in some kind of 'program'.)

function evencheck(n){
    if (n == 0){
        $('#textfield').append('Even');
    }
    if (n == 1 || n == -1){
        $('#textfield').append('Uneven');
    }
    else{
        if(n > 1){
            n -= 2;
            evencheck(n);
        }
        if(n < -1){
            n += 2;
            evencheck(n);
        }
    }

}

I know it can be written shorter, I've made a shorter form of it, but that didn't work on negatives either.

I know the problem is a stack overflow, but why is this happening?

What do you mean it doesn't work for negatives? because it worked for me. — DjaouadNM, Sep 04 '17 at 14:53
It just doesn't work; both chrome and firefox just don't work; chrome gives me an `Uncaught RangeError: Maximum call stack size exceeded` -error, firefox just kinda freezes for a couple seconds. — mr_skeltal, Sep 04 '17 at 14:57
Indeed - I'll change it to odd :-) On an input of `-5` by the way. Even with very small numbers it doesn't work in the page I made for it. — mr_skeltal, Sep 04 '17 at 15:08
Problem solved - the string was the problem, I changed my `prompt('pick a number')` to `Number(prompt('pick a number'))`. — mr_skeltal, Sep 04 '17 at 15:10
@arthur if you move the evencheck out of the if, negate the if and let it return, youve got tail call recursion (?) which can be heavily optimized by the compiler ( no laggin with big nums anymore) — Jonas Wilms, Sep 04 '17 at 15:16
@Jonasw Could you post a snip on how the code would look then? I'm sorry, I'm an absolute noob even to js... Looked up call recursion though, good to know I should write my recursive functions differently. — mr_skeltal, Sep 04 '17 at 15:25

Jonas Wilms · Answer 1 · 2017-09-05T13:35:56.490

1

not an answer but an extended comment

function evencheck(n){
    if (n == 0){
      return $('#textfield').append('Even');
    }
    if (n == 1 || n == -1){
      return $('#textfield').append('Uneven');
    }        
    return evencheck(n > 1? n-2 : n+2);
}

The upper code will probably be faster, as the compiler can optimize it to:

function evencheck(n){
  while(true){
    if (n == 0){
      return $('#textfield').append('Even');
    }
    if (n == 1 || n == -1){
      return $('#textfield').append('Uneven');
    }        
    n = n>1? n -2 : n+2;
  }
}

So youre not filling the function stack ( really huge numbers possible) , and its actually really fast.

More about that

edited Sep 05 '17 at 13:35

answered Sep 04 '17 at 15:30

Jonas Wilms

132,000
20
149
151

Thanks! Smart optimization there :) – mr_skeltal Sep 04 '17 at 15:33
1

That's an awesome solution. – Thijs Sep 04 '17 at 15:39
Two observations: 1) JS engine in Chrome doesn't optimise the code, it is entirely up to you. 2) Don't forget to add a `break` instead of `return` or you'll be waiting a really long time for the method to stop running. Other than that, it does determine if a number is odd or even for larger numbers. – Thijs Sep 04 '17 at 20:19
@thijs why do you know that? The only easy way to check that is to run the code with two different version of chrome and check the time difference. 2) no, theres no need to break if you return. – Jonas Wilms Sep 05 '17 at 05:31
@Jonasw I know Chrome doesn't optimise the method because I get a max call stack size exceeded error when I run the first implementation in Chrome v60 but the second implementation has no problems when `n` is 300000. Second point is my bad, replaced the jQuery code with a `console.log` and by mistake removed the `return` in front of it. – Thijs Sep 05 '17 at 07:05
@thijs oh right :/ , looks like one needs to explicitly return the tail call to make it work... – Jonas Wilms Sep 05 '17 at 13:36

Thijs · Accepted Answer · 2017-09-04T15:14:08.687

Your code seems to work, except for large numbers. Try it with something like -12 or 10 works fine. When you input 30000 it hangs itself. Probably because you call the method recursively too many times.

const
  inputElement = document.getElementById('number-input'),
  checkTrigger = document.getElementById('check-number')
  resultLog = document.getElementById('result');
  
function evencheck(n){
    if (n == 0){
        resultLog.textContent = `${n} is event.`;
    }
    if (n == 1 || n == -1){
        resultLog.textContent = `${n} is unevent.`;
    }
    else{
        if(n > 1){
            n -= 2;
            evencheck(n);
        }
        if(n < -1){
            n += 2;
            evencheck(n);
        }
    }

}
  
function checkInputNumber(event) {
  const
    numberToCheck = parseInt(inputElement.value);
  evencheck(numberToCheck);
}
  
checkTrigger.addEventListener('click', checkInputNumber);


$('#evenrecursive').click(function(){ $('#textfield').append("<p style ='color:blue'>new command: check if number is even.</p>"); var n = prompt('pick a number', ''); evencheck(n); });

#evenrecursive {
border: 1px solid;
min-height: 20px;
width: 100%;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input id="number-input" type="number" />
<button type="button" id="check-number">check</button>
<p id="result"></p>

<div id="evenrecursive">click me for prompt.</div>

I've added your trigger and the problem you're having is type coercion. When the initial value of n is "-10" the code winds up in n += 2, this comes down to n = "-10" + 2 which is "-102" and thus your code never reaches the end.

yep, it works here... Thanks. Doesn't work in my page though. Here's how I make it display on the page: `$('#evenrecursive').click(function(){ $('#textfield').append("
new command: check if number is even.
"); var n = prompt('pick a number', ''); evencheck(n); });`. Is there anything wrong with this? Anyway, good to know the code in itself works :) thanks. — mr_skeltal, Sep 04 '17 at 15:03
I don't think the result of prompt is of type Number, it most likely returns a string. Then again, due to type coercion that shouldn't matter. — Thijs, Sep 04 '17 at 15:04
Changed `prompt('pick a number')` to `Number(prompt('pick a number'))`. It works for negatives now. The '-' must've been the thing which didn't get type-coercion'd to a number I guess... Stupid of me on overlooking that... Thanks! — mr_skeltal, Sep 04 '17 at 15:12
Just added an explanation to the answer why it was happening, glad to hear you had also discovered this on your own. — Thijs, Sep 04 '17 at 15:13

score 0 · Answer 3 · answered Sep 04 '17 at 15:11

0

now it only works for positives. why is this happening?

You might be passing a string, in which case n += 2 does do string concatenation instead of number addition (whereas -= 2 always casts to a number). Try adding

if (typeof n != "number") throw new TypeError("n must be a number");

in the first line of the function, and make sure you do use parseInt or some other suitable parsing method if you take a string input from the user.

answered Sep 04 '17 at 15:11

Bergi

630,263
148
957
1,375

Problem is solved, was indeed type coercion. Dumb overlook by me. I changed `prompt(...)` to `Number(prompt..))`. Solved :D. Thanks! – mr_skeltal Sep 04 '17 at 15:16
Done! I can't upvote, I don't have 15 rep... Answer is accepted though – mr_skeltal Sep 04 '17 at 15:27

Checking for evenness through recursion (Eloquent javascript-exercise)

3 Answers3