Question About Recursion

[NathanOliver]

Hey All

Yesterday I was writing a recursive form of a prime factorization program and I wasn't sure about the syntax I used. the function works as is but I'm curious if I am being redundant or if this is the proper way to code it.

Here is what I came up with

void PrimeFactorize(unsigned int number, vector<unsigned int> & factors)
{
	if (number == 1)
		return;
	if (number % 2 == 0)
	{
		factors.push_back(2);
		return PrimeFactorize(number / 2, factors); // not sure about this
	}
	else
	{
		for (unsigned int i = 3; i <= number; i += 2)
		{
			if (number % i == 0)
			{
				factors.push_back(i);
				return PrimeFactorize(number / i, factors);  // here too
			}
		}
	}
	return;
}

The syntax I am talking about is on lines 8 and 17. I didn't know if I should put the return in or just call the function.

[mrnutty]

Actually, I never seen that before. Usually I just call the function w/o the return
statement. I think you should omit the "return" statement on line 8 and 17, because
that might confuse a reader thinking that it actually returns something.

[Banfa]

I am not convinced by this solution for instance line 17 can be replaced by

number /= i;
i -= 2;

which seems rather simpler and less wasteful of stack space.

The whole point of recursion, in my opinion is to remove iteration (loops) so way recursive function with a loop in it is suspect.

I think the returns look a little strange for a void function I would either leave the out or if I want explicit returns I would put them on the next line.

[NathanOliver]

I admit the returns do look wired but when I get rid of them the program does not work right. Also by using the /= or -= operator causes problems as well. I guess my logic is so messed up that doing it the right way makes it worse :). Maybe we could call this a hybrid function? well thanks guys for the responses I think I'm going to rest on it and try something different tomorrow.

[VernonDozier]

If you have a void function and you want to "return" (i.e. don't execute the code after that line), I'd say your best bet is to break it into two lines:

PrimeFactorize(number / 2, factors);
return;

That gives you the same "short-circuit" options that a regular "return" gives you, but is less confusing.

[NathanOliver]

I did that about 30 minutes ago after it popped into my head but thanks Vernon for pointing that out.

[abhimanipal]

You are on the right track but your implementation can be made more efficient. I have written down some sample code for you. So if you want to find the prime factorization of 12 the call to the function will be

primeFactors(12,v1,2);

void primeFactors(int num,vector<int>& v1,int start)
{
     int i=0;
     
     if(num<=1)
           return ;
     else
     {
            if(num%start==0)
            {
                // We come here when start is a factor of num. So if num is 12 and start is 2, you include 2 in the vector list and call the function again. What will the new arguments be ? 
            } 
            else
            {
              //We come here when start is not a factor of num. So if the num is 13, 2 is not a factor of 13 so we call the function again. What will the arguments be in this case ? 
            }
     }
}

[NathanOliver]

void primeFactors(int num,vector<int>& v1,int start)
{
     int i=0;
     
     if(num<=1)
           return ;
     else
     {
            if(num%start==0)
            {
                v1.push_back(start);
                primeFactors(num / start, v1, start)
            } 
            else
            {
              primeFactors(num, v1, start++)
            }
     }
}

i believe this is what you are hinting at correct?

[NathanOliver]

The reason I was using a for loop was to reduce the number of function calls. If it is not that much of an overhead then I would gladly change my code to not have a for loop.

[abhimanipal]

Yes this was what I was hinting at ....
Yes using the recursive method leads to huge number of function calls( I take back my earlier comment). But if you want to use recursion to solve your problem you have to accept that penalty. It is very rare that recursive solution is more faster than iterative solution

[NathanOliver]

Thanks for your replies abhimanipal. I'll leave this post unsolved for now in case anyone else would like to chime in. Thanks guys.