Recursively finding prime factors

Question

I am starting to teach myself C and am trying to build a group of useful functions and programs for future reference. If relevant, this is C99.

Here is my most recent iteration of the program. At the output, I want to get the prime factorization of a number n. As is, however, I get a list of all factors, and no factors are repeated. I included some print statements to try and debug, and have found that the error is with the recursion, but can't figure out how to interpret it further. I previously tried making the recursive function of type int, but had difficulties getting it to work with the array p.

n is the number that I am trying to factor
p is an array for storing the found primes
j is an index for p
c is the number that I am testing as a divisor to n

I am aware that there are probably more efficient ways to declare p to save memory, but since this is mainly for reference, memory is not a huge concern.

I found these questions but don't think that they answer my question

finding greatest prime factor using recursion in c :This question is about crashing code. Mine compiles, runs, and produces reasonably sensible output, I'm just wondering why the output isn't what I expect.
is there ever a time you would not use recursion? [closed] :This indicates that recursion is not a good choice for prime factorization- I don't know, but suspect that this would also apply to C. Since this is for reference, I don't think it is a huge issue. If you disagree, please explain why.

My main questions are these: Why does the output show all factors of n? Why does it not repeat the prime factors? What do I have to do to fix it?

  #include <stdio.h>

  #define NELEMS(x)  (sizeof(x) / sizeof((x)[0]))

  void factors(int n, int p[], int j) {
  /// if n is divisible by c, store c, and continue with n/c
      int c;
      for (c=2; c < n; c++) {
          if (c > n) break;
          if (n%c == 0) {
              p[j] = c;
              printf("%d has been added to p \t", c);
              printf("n has been reduced to %d \t", n/c);
              printf("j is %d \n", j);
              j++;
              if (n == c) break;
              factors(n/c, p, j);
          }
      }
  }

  int main() {
      /// set up number to factor, and array to hold factors
      int n = 24;
      int p[n/2];
      int i=0;
      for (i=0; i<NELEMS(p); i++) {
          p[i]=0;
      }

      int j = 0;
      factors(n, p, j);

      printf("the prime factors of %d are:\n",n);
      for (i=0; i<NELEMS(p); i++) {
          printf("%d \n", p[i]);
      }

  }

"This indicates that recursion is not a good choice for prime factorization" Indeed, recursion is bad for pretty much any task you can think of. Recursion has incredibly narrow use, the only uses for it I can come up with is storage-optimizing binary trees and some math simulation theory tasks. In 99% of all cases, recursion makes algorithms slow, memory-consuming an dangerous. It is also most often hard to read. Despite its uselessness, schools and books tend to focus heavily on recursion, because "it looks fancy". In the real world though, you should avoid it like the plague. — Lundin, Mar 23 '17 at 10:47
@Lundin that might be true in C but that's certainly not the case in other languages where recursion is your primary (and idiomatic) looping construct — Mulan, Mar 23 '17 at 13:17
@naomik It's just because the programmers of higher level languages generally have no clue what an ineffective, dangerous mess recursion creates. Programmers of such languages generally don't have a clue about how their source code translates to machine code. — Lundin, Mar 23 '17 at 14:08
Please, use names for the variables that explain what they are used for. it's difficult to remember what are the parameters used for, if you call them `a`, `b`, and `c`.... — Luis Colorado, Jul 11 '17 at 08:12
@LuisColorado I was trying to use variable names that were short but retained some meaning: p for prime, c for candidate, n for number. In the future I'll make this more explicit. — fyzx92, Jul 27 '17 at 12:25

Quentin Laillé · Answer 1 · 2017-09-21T08:15:22.657

From This answer:

why does recursion cause stackoverflow so much more than loops do

Because each recursive call uses some space on the stack. If your recursion is too deep, then it will result in StackOverflow, depending upon the maximum allowed depth in the stack.

When using recursion, you should be very careful and make sure that you provide a base case. A base case in recursion is the condition based on which the recursion ends, and the stack starts to unwind. This is the major reason of recursion causing StackOverflow error. If it doesn't find any base case, it will go into an infinite recursion, which will certainly result in error, as Stack is finite only.

-

It appears that your for is in the way, c will increment, and wont check that same value again.

For instance, if the input is 8, we want (2,2,2) and not (2,4).

I would recommend replacing your if (c%n ==0) by a while, don't forget to replace the value of n in that while, you don't want to loop in that.

This appears to be a good answer :

int primes(int nbr, int cur)
{
  if (cur > nbr)
    return (0);
  else
    {
      if (nbr % cur == 0 && isprime(cur) == 1)
        {
          printf("%d\n", cur);
          return (primes(nbr / cur, 2));
        }
      return (primes(nbr, cur + 1));
    }
}

Call that function with cur = 2 in your main

JeremyP · Answer 2 · 2017-03-23T11:56:41.640

Edit It occurs to me that the smallest factor of n is guaranteed to be prime, so I have edited the answer accordingly.

Why does the output show all factors of n?

Because you test if c is a factor of n and add it to the array p whether c is prime or not. Then you carry on testing numbers above c, even multiples of c.

Why does it not repeat the prime factors?

Because when you find a number c that is a factor, you don't necessarily inspect it to find out if it is a compound number itself.

After adding c to p, you need to recursively call factor on (n / c) and then stop.

Here is roughly what you need (but not tested or even compiled)

int factorise(int n, int p[], int j)
{
    int factorsFound = 0;

    for (c = 2 ; c * c <= n && factorsFound == 0 ; ++ c)
    {
        if (n % c == 0)
        {
            p[j] = c;
            factorsFound = factorise(n / c, p, j + 1) + 1;
        }
    }
    if (factorsFound == 0) // n is prime
    {
        p[j] = n;
        factorsFound = 1;
    }
    return factorsFound;
}

Also in a real solution, you probably want to pass the size of p so that you can detect if you run out of space.

Just for fun, since nobody else has posted it yet, here is a non recursive solution. It's actually the same as above but the recursion has been transformed into a loop.

int factorise(int number, int p[])
{
    int j = 0;

    for (int c = 2, int n = number ; n > 1 ; )
    {
        if (n % c = 0)
        {
            p[j++] = c;
            n = n / c;
        }
        else
        {
            c++;
        }
    }
    return j;
}

I disagree with some of Lundin's comments about recursion. Recursion is a natural way of breaking a problem down into easier subtasks but in C it is undeniably less efficient, especially in terms of stack space and in this particular case, the non recursive version is simpler.

I'm curious why here you return j? wouldn't it be possible to remove that statement and make the whole function of type void? — fyzx92, Apr 10 '17 at 15:41
@fyzx92 j is the count of factors found. It's is probably going to be useful to the caller to know how many factors there are and you don't then have to iterate the array looking for a sentinel value. — JeremyP, Apr 10 '17 at 15:49

score 0 · Accepted Answer · answered Mar 23 '17 at 11:37

You have already been told in comments that this algorythm is poor, which is an evidence here. And you really should learn to use a debugger: running this through a debugger immediately shows where the problems are.

That being said, your main problem here is what to do when the recursive functions return?. You failed to ask yourself this question which is a must in recursion, and simply continue in sequence, which is plain wrong because you will reuse a number that has already been processed in the recursive calls. So you must add a return line immediately after recursively calling factors.

Once this is done, there is another minor problem (that a debugger would make evident), you only search factors strictly lesser that n. So you miss the last prime factor...

With those 2 immediate fixes, your code becomes:

void factors(int n, int p[], int j) {
  /// if n is divisible by c, store c, and continue with n/c
      int c;
      for (c=2; c <= n; c++) {
          if (c > n) break;
          if (n%c == 0) {
              p[j] = c;
              printf("%d has been added to p \t", c);
              printf("n has been reduced to %d \t", n/c);
              printf("j is %d \n", j);
              j++;
              if (n == c) break;
              factors(n/c, p, j);
              return;
          }
      }
  }

But IMHO p[j] = c; should become *p = c; and factors(n/c, p, j); should become factors(n/c, p+1, j);. Said differently you pass directly a pointer to the next slot.

If you pass the pointer to the next slot, you do not need to pass j which is the offset of the next slot from p. — JeremyP, Mar 23 '17 at 11:40
But that's only debugging info. You could print the value of p instead. — JeremyP, Mar 23 '17 at 11:44

Recursively finding prime factors

3 Answers3