DaniWeb Forum Index > Software Development > C++

Recursive Factorial

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Jul 2008

Posts: 32

Reputation: coveredinflies is an unknown quantity at this point

Solved Threads: 0

coveredinflies coveredinflies is offline

Offline

Light Poster

Recursive Factorial

Aug 15th, 2008

Hi, I am sure you have all seen the recursive factorial program.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int factorial(int number) {
	int temp;
 
	if(number <= 1) return 1;
 
	temp = number * factorial(number - 1);
	return temp;
}
int factorial(int number) {
	int temp;

	if(number <= 1) return 1;

	temp = number * factorial(number - 1);
	return temp;
}

" Once at 1, the values are returned to the previous factorial call and multiplied together."

Could someone explain this to me please, I know it works but when I first read the code I thought it would always return 1 since as I understand it as soon as a function gets to a return value it returns that number (or other type). Since you keep lowering number till you get to 1 I can't see how this doesn't always return 1.

Thanks.

•

Join Date: Aug 2005

Posts: 5,266

Reputation: iamthwee is a splendid one to behold

Solved Threads: 377

iamthwee

Offline

Posting Expert

Re: Recursive Factorial

Aug 15th, 2008

Maybe it would be easier if you thought about the code like so:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int factorial ( int number )
{
  int temp;
 
  if ( number <= 1 )
  {
    return 1;
  }
  else
  {
    temp = number * factorial ( number - 1 );
    return temp;
  }
}
int factorial ( int number )
{
  int temp;

  if ( number <= 1 )
  {
    return 1;
  }
  else
  {
    temp = number * factorial ( number - 1 );
    return temp;
  }
}

Last edited by iamthwee; Aug 15th, 2008 at 8:35 am.

*Voted best profile in the world*

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: Recursive Factorial

Aug 15th, 2008

Don't worry, simply form a habit to read (then invent) recursive algorithmes (apropos, never calculate factorial in this manner

).
How about:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int factorial(int n)
{
    return n <= 1? 1: n*factorial(n-1);
}
int factorial(int n)
{
    return n <= 1? 1: n*factorial(n-1);
}

Simple and clear code (with guarantee of as usually undetected integer overflow

)...

Last edited by ArkM; Aug 15th, 2008 at 11:30 am.

•

Join Date: Mar 2008

Posts: 31

Reputation: scream2ice is an unknown quantity at this point

Solved Threads: 0

scream2ice scream2ice is offline

Offline

Light Poster

Re: Recursive Factorial

Aug 15th, 2008

why don't u trace for a number like 4?
of course the code u've come up with 'is' actually more complicated than a simple code for a factorial should be! but tracing it will help

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int factorial(int number) {
	int temp;
 
	if(number <= 1) return 1;
 
	temp = number * factorial(number - 1);
	return temp;
}
int factorial(int number) {
	int temp;
 
	if(number <= 1) return 1;
 
	temp = number * factorial(number - 1);
	return temp;
}
int factorial(int number) {
	int temp;

	if(number <= 1) return 1;

	temp = number * factorial(number - 1);
	return temp;
}
int factorial(int number) {
	int temp;

	if(number <= 1) return 1;

	temp = number * factorial(number - 1);
	return temp;
}

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: Recursive Factorial

Aug 15th, 2008

Yet another productive method: try to "unwind" solution from the END of recursion.
For example, in factorial case:

When the function knows the answer? Of course, if n <= 1 - factorial is equal to 1 by definition! OK, write the first statement:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int factorial(int n)
{
    if (n <= 1)
        return 1;
    // But what else?...
}
int factorial(int n)
{
    if (n <= 1)
        return 1;
    // But what else?...
}

Let's continue. Suppose we HAVE a function to calculate factorial for all small numbers < n.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
in factorial(int n)
{
    if (n < 1)
        return 1; // OK, it's our point of rest...
    // We are on terra incognita now, but
    // let's remember school math...
    // Factorial definition helps:
    return factorial(n-1) * n;
}
in factorial(int n)
{
    if (n < 1)
        return 1; // OK, it's our point of rest...
    // We are on terra incognita now, but
    // let's remember school math...
    // Factorial definition helps:
    return factorial(n-1) * n;
}

Stop. See how the land lies.

We are trying to call factorial for lesser than n number then more lesser and so on.
We are going to the bottom - of what? Where is this bottom?

Aha, come back to the 1st and 2nd line of the function body. That's a bottom! After that we will rise to the surface, back to starting recursion level, and - hurrah - we know factorial(n-1) - that's all, all done.

It looks like a trick or abstraction: we have no function yet but operate with its call(s) to build its body...

But it's the power of recursive solutions.

•

Join Date: Mar 2008

Posts: 31

Reputation: scream2ice is an unknown quantity at this point

Solved Threads: 0

scream2ice scream2ice is offline

Offline

Light Poster

Re: Recursive Factorial

Aug 16th, 2008

with the recursive functions you should always have a stop point somewhere in ur function otherwise it will go on forever. Your stop point in this case is the "return 1" which means that you can only exit the program when you have reached the number 1 (because u've got the (n<=1) condition)---it is ur only way to end the recursion
'return 1' here means in fact 'return true'....try replacing it ...it still works
bcuz you are not actually returning the 'number' 1 but you are telling your compiler that it is now ok to exit the program....this is where i want my code to end
but do u kno why if we put 'return 0' instead of 'return 1', the output will be zero?
'return 0' can actually be equivalent to 'return false', so the recusion ends but a false end

•

Join Date: Jul 2008

Posts: 32

Reputation: coveredinflies is an unknown quantity at this point

Solved Threads: 0

coveredinflies coveredinflies is offline

Offline

Light Poster

Re: Recursive Factorial

Aug 16th, 2008

Hey thanks for the replies, I totally wasn't getting it and didn't understand your first few posts then I was reading fifth post and it clicked.

the last return 1 returns to the previous function call not to the main function. thank you again I was getting really frustrated. so obvious in hindsight!