5

I've been trying to compare functions speed in C and there is something I cannot understand,

I tried to get sum of prime numbers(1 to 100000)

in recursive I get 2.1.... sec

int sumOfPrime(unsigned int top)
{
    if( top % 2 == 0 ) top -= 1;
    static int total = 2; // sum of prime numbers
    int i;
    int control=0; // prime or not
    if( top == 2 | top < 2) return total; 
    for (i = 3; i < (top/2)+1; i++)
    {
        if( top % i == 0 ) // if there is a multiple
        {
            control++;
            break;
        }
    }
    if( control == 0 ){
        total += top;
    }
    return sumOfPrime(top-2); 
}

in iterative which is O(n^2) I get 1.14 sec

int sumOfPrime(unsigned int top)
{
    unsigned int total = 2;
    int count;

    int i,j;

    for (i = 3; i < top; i+=2)
    {
        count = 0;
        for (j = 3; j < (i/2)+1; j+=2)
        {
            if( i % j == 0 )
            {
                count++;
                break;
            }
        }
        if( count == 0 ){
            total += i;
        }
    }

    return total;
}

and then I tried it in tail recursive and still I got 2.1 almost exactly same time,

int sumOfPrime(unsigned int top,unsigned int total)
{
    if( top % 2 == 0 ) top -= 1;
    //static int total = 2; 
    int i; // for for loop
    int control=0; // prime or not
    if( top == 2 | top < 2) return total+2; 
    for (i = 3; i < (top/2)+1; i++) 
    {
        if( top % i == 0 ) // if there is a multiple
        {
            control++; // add +1 to control
            break;
        }
    }
    if( control == 0 ){ // if its primme
        total += top;
    }
    return sumOfPrime(top-2,total);
}

Here is the thing we use recursive for speed in some situations like merge-sort so what is the situations like that ?

Is there a some spesific rules about when to use it for speed ? or What am I missing ? I'm really more comfortable recursive than iterative and I really want to use it but this speed diffrences gives me stomachache.

Vivian Maya
  • 498
  • 1
  • 4
  • 11
  • 1
    "We use recursive for speed" ? No. See http://stackoverflow.com/questions/15688019/recursion-versus-iteration – Denys Séguret Nov 19 '14 at 16:04
  • 2
    Are you sure that the compiler actually optimizes tail recursion? And why would we use recursion only for "speed"? It's also a very good way to emulate a stack. – Some programmer dude Nov 19 '14 at 16:05
  • @joachimPileborg Could you explain it please, what do you mean by emulating stack ? thanks for your attention – Vivian Maya Nov 19 '14 at 16:09
  • 2
    @VivianMaya, I think Joachim Pileborg is saying that recursion can emulate a stack data structure fairly well. Essentially each call is like adding an element to the stack and every time you return it's like popping an element off the stack. So there's uses for recursion that have nothing to do with speed but are used more for programming clarity. Does that make more sense? – shuttle87 Nov 19 '14 at 16:14
  • 2
    I answered [a very similar question about quicksort in java](http://stackoverflow.com/q/12553238/572670). tl;dr: Recursion could be faster than iteration (regardless of what the books say) when the iterative solution is merely trying to mimic the recursion, and is using a much less optimized stack to do so. – amit Nov 19 '14 at 16:14
  • @shuttle87 now its more clear thank you... – Vivian Maya Nov 19 '14 at 16:18
  • @amit I got what your point fine enough thank you for your attention – Vivian Maya Nov 19 '14 at 16:19
  • Are you compiling with optimization? Normally, recursion benefits more than iteration. By the way, you only need to check factors up to the square root of the possible prime, not half of it (don't compute the square root; check if `factor * factor < prime`), which will improve your performance a lot (in both iterative and recursive). – rici Nov 19 '14 at 17:42
  • what is the optimization ? is there something for compiler ? can you explain it please... – Vivian Maya Nov 20 '14 at 15:14

0 Answers0