Thread: Recursion Madness

  1. #1
    Registered User
    Join Date
    Nov 2013
    Posts
    11

    Recursion Madness

    Hello I am dire need of help. I have gone to many different variations some code but I can't seem to come up with a solution. The code is suppose to do this:
    Write a function that finds all the prime factors of a number N, stores it to an array and returns a pointer to that array.(The returned memory will be freed for you in the main.) Also, since the length of the array is unknown a priori, it is convenient to terminate the array of factors with a 0.
    It is remarkable that in order to find prime factors with recursion you do not need to use the helper functionisPrime from one of the previous labs to decide if numbers are prime (nor should you!).

    Can someone verbally explain to me step by step how to create a function that does this?

  2. #2
    Registered User
    Join Date
    Nov 2013
    Posts
    11
    Code:
    int main(int argc, char *argv[]){
        int M, *x, *p, y[101], m, i;
        double k;
        sscanf(argv[1], "%d", &M);
    /*
        //test sumPowers
        k = 1.0;
        printf("Power of first %d integers to %lf is %lf\n",M,k, sumPowersRec(M,k));
        k = 3.4;
        printf("Power of first %d integers to %lf is %lf\n",M,k, sumPowersRec(M,k));
        k = 5.123;
        printf("Power of first %d integers to %lf is %lf\n",M,k, sumPowersRec(M,k));
    
    
        //test saveMoney
        printf("Money saved after %d years with initial deposit $1000,\n annual deposits $100 and interest rate 0.01 is $%lf\n",M, saveMoney(1000,100, 0.01,M));
        printf("Money saved after %d years with initial deposit $5234,\n annual deposits $600 and interest rate 0.02 is $%lf\n",M, saveMoney(5234,600, 0.02,M));
        printf("Money saved after %d years with initial deposit $123,\n  annual deposits $45 and interest rate 0.0067 is $%lf\n",M, saveMoney(123,45, 0.0067,M));
        printf("Money saved after %d years with initial deposit $34567,\n annual deposits $9876 and interest rate 0.00567 is $%lf\n",M, saveMoney(34567,9876, 0.00576,M));
    
    
        //test Pascal's triangle
        for(m=0; m <= M; m++)
        {
            pascalsTriangle(y, m);
            for(i=0; i<(M-m)*2; i++)  printf(" ");
            for(p = y; p <= y+m; p++)
                printf("%4d", *p);
            printf("\n");
        }
     */
        //test prime factors
        x = primeFactors(M);
        for(p = x; *p != 0; p++)
            printf("%d  ", *p);
        printf("\n");
        free(x);
        return 0;
    The main function looks like that.

  3. #3
    Registered User
    Join Date
    Nov 2013
    Posts
    11
    Code:
     int *primeFactors(int N){
        int nAlloc =1, i, *p;
        int *x = (int *)malloc(2*nAlloc*sizeof(int));
        
        if(N==1)
        {
            x[0] =1;
            x[1] = 2;
        }
        for(i = 2; i <= N/2; i++)
        {
            if((N%i)==0)
            {
                nAlloc =+1;
                x[nAlloc] = i;
                x = realloc(x,nAlloc*sizeof(int));
                x =primeFactors(N/i);
            }
        }
    return p;

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Do you know how to factor a number into primes your own self (without a computer)? If so, well, that's basically your algorithm sorted.

  5. #5
    Registered User
    Join Date
    Nov 2013
    Posts
    11
    But with it comes to malloc and realloc, I basically keep on overwriting the values and all that prints is an empty array

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So what purpose does p have in your code?

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    If I was doing this problem I'd probably begin by doing it without worrying about storing it in array; i.e. just recursively print out the prime factors (from within the primefactors function). After that's working properly I'd then move onto storing the results in an array.

    Edit: I should have added that your recursive function (ignoring the memory/array issue) is currently incorrect.
    Last edited by Hodor; 12-07-2013 at 11:15 PM.

  8. #8
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Since I had nothing to do I went ahead and implemented your function. I won't post the function here but this is my main() with tests... it may be helpful in some way. I'm not suggesting that you use this main function in your submission but it may help you test.

    To be safe you'd really want to test a whole bunch of numbers, but I leave that to you (I feel I've done too much already, but as I said I was bored)

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    int main(void)
    {
        int *pfacts, n, product;
        
        n = 12345678;
        
        pfacts = primefactors(n);
        
        if (pfacts && pfacts[0] != 0) {
            size_t pos;
            product = 1;
            for (pos = 0; pfacts[pos] != 0; pos++) {
                assert(isPrime(pfacts[pos]));              /* Each factor must be prime */
                printf("Factor: %d\n", pfacts[pos]);
                product *= pfacts[pos];
            }
            
            /* The product of the factors must equal the original number */
    
            printf("\nProduct is: %d\n", product);
            printf("Product test %s\n", product == n ? "passed." : "FAILED!");
        }
        free(pfacts);
        
        return 0;
    }

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by Casanova411 View Post
    It is remarkable that in order to find prime factors with recursion you do not need to use the helper function isPrime from one of the previous labs to decide if numbers are prime (nor should you!).
    It's not quite so remarkable, and the helper function isPrime would not be needed if you found the prime factors with iteration either.

    Are you sure this function is to be implemented via recursion? If so, it's going to be somewhat inefficient compared to an iterative approach.
    Last edited by rcgldr; 12-08-2013 at 12:46 PM.

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Either the OP solved this or gave up. Here's an example that creates the array in reverse order. It's not efficient, but it is recursive.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int * FindFactors(int n){
    int *p;
    int i, j;
        if(n < 2){
            p = malloc(sizeof(int));
            p[0] = 0;
            return p;
        }
        for(i = 2; i <= n; i++){
            if((n%i) == 0){
                n /= i;
                p = FindFactors(n);
                for(j = 0; p[j]; j++);
                p = realloc(p, (j+2)*sizeof(int));
                p[j] = i;
                p[j+1] = 0;
                return(p);
            }
        }
        return(NULL);   /* this statement never reached */
    }           
    
    int main(){
    int *p, *q;
        q = p = FindFactors(120);
        while(*p){
            printf("%3d ", *p);
            p++;
        }
        printf("\n");
        free(q);
        return 0;
    }

  11. #11
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by rcgldr View Post
    Either the OP solved this or gave up. Here's an example that creates the array in reverse order. It's not efficient, but it is recursive.
    Well, I kind of "cheated" by using a wrapper. Plus it's a mess... oh well

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int primefactors_r(unsigned n, int **mem, size_t *sz)
    {
        int i, maxn;
        
        if (n < 2)
            return 0;
        
        maxn = n / 2;
        for (i = 2; i <= maxn; i++) {
            if (n % i == 0) {
                if (primefactors_r(i, mem, sz)) {
                    (*mem)[*sz - 1] = i;
                    *mem = realloc(*mem, ++(*sz) * sizeof(**mem));
                }
                if (primefactors_r(n / i, mem, sz)) {
                    (*mem)[*sz - 1] = n / i;
                    *mem = realloc(*mem, ++(*sz) * sizeof(**mem));
                }
                break;
            }
        }
        /* return 0 (false) if no 'lower' primefactors found;
         * i.e. the above loop didn't terminate early */
        return i > maxn;
    }
    
    int *primefactors(unsigned n)
    {
        int *mem = NULL;
        size_t sz = 1;
        
        if ((mem = malloc(sizeof *mem * sz)) == NULL)
            return NULL;
        
        if (n < 4) {
            mem[0] = 0;
            return mem;
        }
        
        primefactors_r(n, &mem, &sz);
        if (mem) {
            mem[sz - 1] = 0;
        }
        return mem;
    }
    
    
    int main(void)
    {
        int *pfacts, n, product;
        
        n = 120;
        
        pfacts = primefactors(n);
        
        if (pfacts && pfacts[0] != 0) {
            size_t pos;
            product = 1;
            for (pos = 0; pfacts[pos] != 0; pos++) {
                printf("Factor: %d\n", pfacts[pos]);
                product *= pfacts[pos];
            }
            printf("\nProduct is: %d\n", product);
            printf("Product test %s\n", product == n ? "passed." : "FAILED!");
        }
        free(pfacts);
        
        return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. static lib madness
    By MK27 in forum C++ Programming
    Replies: 2
    Last Post: 03-20-2010, 01:06 PM
  2. Multithreading Madness?
    By leeor_net in forum Game Programming
    Replies: 4
    Last Post: 09-11-2009, 12:46 AM
  3. pointer madness
    By moonlord in forum C Programming
    Replies: 11
    Last Post: 08-22-2005, 08:58 AM
  4. memcpy madness
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 08-25-2003, 08:56 AM

Tags for this Thread