Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I understand that because of Javascript's single-threaded execution, long loops or recursive calls could make the browser unresponsive while they execute.

I thought about simulating recursion using setTimeout with a delay of 0, so as to queue the next call to execute as soon as possible.

Here's an example comparing a standard recursive factorial function with an attempt to do the same thing but using setTimeout:

function rFactorial(num)
{
    if (num === 0) return 1;
    else return num * rFactorial( num - 1 );
}

function tFactorial(num, callback, acc) {
    acc = acc || 1;
    if (num === 0) {
        callback(acc);
    }
    else {
        setTimeout(function() {
            tFactorial(num-1, callback, acc*num);
        }, 0);
    }
}

I tested this using the following test:

for (var x = 1; x < 20; x += 1) {
    tFactorial(x, (function(n) {
        return function(result) {
            console.log(rFactorial(n) === result)
        };
    })(x));
}

This worked for that range of numbers, although for higher numbers the two functions seem to give different results. for example, for 100, sFactorial gives 9.332621544394418e+157, while rFactorial gives 9.33262154439441e+157.

So I have two questions. (1) Is this a good approach, can anyone suggest any improvements etc. (2) can anyone shed any light on why the two functions give the same results for lower numbers but different results for higher numbers?

share|improve this question
    
It may not be directly because of recursion. It may be how you are passing the values per iteration plus the fact that JS is known to mishandle floats. –  Joseph the Dreamer Feb 1 '13 at 15:09
    
@JosephtheDreamer "JS is known to mishandle floats" ? What does that mean ? –  dystroy Feb 1 '13 at 15:12
1  
You may want to look at this: stackoverflow.com/questions/1458633/… –  Dimitry Feb 1 '13 at 15:15
1  
JS is known to mishandle floats is FUD. Get your facts straight. –  Florian Margaine Feb 1 '13 at 15:31
4  
I was discussing the issue with a clever guy on Stack Overflow, and he found the difference in results is because of differences in the order of multiplication. A simple example: 0.1 * 0.2 * 0.3 yields a different result than 0.3 * 0.2 * 0.1, because intermediate results are different. –  Kendall Frey Feb 1 '13 at 16:30
show 5 more comments

1 Answer

up vote 3 down vote accepted

A few observations :

Numbers in javascript are IEE754 double precision float. All of them. There is no integer type. Which means that only 53 bits are available to describe the integer part. So it doesn't make sense to try to do integer operations on numbers bigger than that. Your numbers are wayyy too big and the results will be undefined. If you want to compute bigger numbers, you'll need to define your own format, you can't use the native numbers of javascript.

Using setTimeout or using a recursion might be amusing solutions but they're not terribly efficient (at least until we have tail call optimization in javascript). You'd better use a simple boring loop.

share|improve this answer
    
"using a recursion might be amusing solutions but they're not terribly effective". Even if the aim of the exercise is to prevent the interface freezing while a calculation completes (perhaps not applicable to this function, but can happen), rather than to compute the function as fast as possible? Or would it be better just to use a web worker? –  samfrances Feb 1 '13 at 15:46
1  
Your computation won't freeze the computer if you try to compute numbers smaller than 2^52 : factorial grows very fast. If you have long computations (which I hadn't thought was the problem), then yes you might use setTimeout or a webworker. –  dystroy Feb 1 '13 at 15:49
    
I see. I was only using factorial composition as an example of a recursive function. I was trying to find a general tactic for carrying out recursive computations that might take a long time to complete without freezing the page. Factorial was just the first recursive function that came to mind (although once I noticed the bug in my example, I was keen to understand why it was there). –  samfrances Feb 1 '13 at 15:53
2  
@samfrances Breaking out of deep calculation and splitting work through setTimeout is a known technique but it's not too effective any more. In new browsers you should use Web Workers for this sort of thing instead.Like dystroy said it doesn't make sense to try to do integer operations on numbers this big. –  Benjamin Gruenbaum Feb 1 '13 at 16:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.