2

have wrote the code for what i see to be a good algorithm for finding the greatest prime factor for a large number using recursion. My program crashes with any number greater than 4 assigned to the variable huge_number though. I am not good with recursion and the assignment does not allow any sort of loop. 

#include <stdio.h>

long long prime_factor(int n, long long huge_number);

int main (void)
{
    int n = 2;
    long long huge_number =  60085147514;
    long long largest_prime = 0;

    largest_prime = prime_factor(n, huge_number);
    printf("%ld\n", largest_prime);

    return 0;
}

long long prime_factor (int n, long long huge_number)
{
    if (huge_number / n == 1)
        return huge_number;
    else if (huge_number % n == 0)
        return prime_factor (n, huge_number / n);        
    else
        return prime_factor (n++, huge_number);
}

any info as to why it is crashing and how i could improve it would be greatly appreciated.

Tristan Pearce
  • 89
  • 1
  • 3
  • 12

4 Answers4

1

You meant n+1 instead of n++. n++ increments n after using it, so the recursive call gets the original value of n.

Borealid
  • 95,191
  • 9
  • 106
  • 122
  • i just tried both ways and it still crashes. using ++n mading it take a few extra seconds though. – Tristan Pearce Jan 30 '12 at 02:30
  • @TristanPearce Yes, `++n` would work, but keep in mind that the particular instance of `n` which is getting incremented would never be used again (since the call in which it is a formal parameter returns immediately after making the recursive invocation). – Borealid Jan 30 '12 at 02:30
  • @TristanPearce The code is actually correct with `++n` or `n+1`. Your stack just can't handle the `huge_number` you gave it. Try a smaller number - it works for dozens now. – Borealid Jan 30 '12 at 02:31
  • @TristanPearce Last hint: try printing `n` and `huge_number` at the top of `prime_factor`. That way you can watch the code do its thing as it runs. – Borealid Jan 30 '12 at 02:31
  • That will still blow out the stack, simply because the vast number of recursions are of the n++ variety, not the huge /= n variety. The last factor-find of that number will need about ten million stack levels. – paxdiablo Jan 30 '12 at 03:00
  • i have no idea how to lower the amount of recursive calls at this point. i know the chance of it working with the huge number is low because it crashes with just 5 which i dont understand. – Tristan Pearce Jan 30 '12 at 03:08
  • @TristanPearce With the change I suggested, it does not crash with five. But if you want it work with larger numbers, use the *Euclidean Algorithm* instead of what you've got. – Borealid Jan 30 '12 at 03:10
1

You are overflowing stack, because n++ post-increments the value, making a recursive call with the same values as in the current invocation.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
1

Even fixing the problem of using post-increment so that the recursion continues forever, this is not a good fit for a recursive solution - see here for why, but it boils down to how fast you can reduce the search space.

While your division of huge_number whittles it down pretty fast, the vast majority of recursive calls are done by simply incrementing n. That means you're going to use a lot of stack space.

You would be better off either:

  • using an iterative solution where you won't blow out the stack (if you just want to solve the problem) (a); or
  • finding a more suitable problem for recursion if you're just trying to learn recursion.

(a) An example of such a beast, modeled on your recursive solution, is:

#include <stdio.h>

long long prime_factor_i (int n, long long huge_number) {
    while (n < huge_number) {
        if (huge_number % n == 0) {
            huge_number /= n;
            continue;
        }
        n++;
    }
    return huge_number;
}

int main (void) {
    int n = 2;
    long long huge_number =  60085147514LL;
    long long largest_prime = 0;

    largest_prime = prime_factor_i (n, huge_number);
    printf ("%lld\n", largest_prime);

    return 0;
}

As can be seen from the output of that iterative solution, the largest factor is 10976461. That means the final batch of recursions in your recursive solution would require a stack depth of ten million stack frames, not something most environments will contend with easily.

If you really must use a recursive solution, you can reduce the stack space to the square root of that by using the fact that you don't have to check all the way up to the number, but only up to its square root.

In addition, other than 2, every other prime number is odd, so you can further halve the search space by only checking two plus the odd numbers.

A recursive solution taking those two things into consideration would be:

long long prime_factor_r (int n, long long huge_number) {
    // Debug code for level checking.

    // static int i = 0;
    // printf ("recursion level = %d\n", ++i);

    // Only check up to square root.

    if (n * n >= huge_number)
        return huge_number;

    // If it's a factor, reduce the number and try again.

    if (huge_number % n == 0)
        return prime_factor_r (n, huge_number / n);

    // Select next "candidate" prime to check against, 2 -> 3,
    //   2n+1 -> 2n+3 for all n >= 1.

    if (n == 2)
        return prime_factor_r (3, huge_number);

    return prime_factor_r (n + 2, huge_number);
}

You can see I've also removed the (awkward, in my opinion) construct:

if something then
    return something
else
    return something else

I much prefer the less massively indented code that comes from:

if something then
    return something
return something else

But that's just personal preference. In any case, that gets your recursion level down to 1662 (uncomment the debug code to verify) rather than ten million, a rather sizable reduction but still not perfect. That runs okay in my environment.

Community
  • 1
  • 1
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • it is an assignment based on recursion in which i cannot use any form of looping. this is what essentially has me stuck. – Tristan Pearce Jan 30 '12 at 03:07
  • @TristanPearce, you can lower the recursion level requirement using two simple tricks (1) checking only 2 and the odd numbers, and (2) only checking up to the _square root_ of the number (this ones the real winner) - see the update. – paxdiablo Jan 30 '12 at 03:36
  • thank you so much. I knew there was something to do with the square root based upon research online. That makes a lot more sense than checking all numbers. – Tristan Pearce Jan 30 '12 at 03:46
  • quick question to avoid compiler warnings. Is it proper to use %lld for long long variables? – Tristan Pearce Jan 30 '12 at 03:50
  • @TristanPearce, yes, you should be using lld for long long types. – paxdiablo Jan 30 '12 at 03:57
  • @TristanPearce Note that a recent enough gcc with `-O3` transforms the (tail) recursive function into a loop. And the computation finishes almost instantaneously since ~5.5 million iterations is not much. Of course the square-root and oddness optimisations are still good, but with a decent compiler, you don't need to worry about stack frames *in such cases as this*. – Daniel Fischer Feb 01 '12 at 12:37
0

the crash reason is stack overflow. I add a counter to your program and execute it(on ubuntu 10.04 gcc 4.4.3) the counter stop at "218287" before core dump. the better solution is using loop instead of recursion.

Tony Bai
  • 151
  • 2
  • 6