Ad:

C++ Discussion Thread
Unsolved
Views: 8760

Aug 15th, 2008

Recursive Factorial

Expand Post »

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

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.

Similar Threads

Factorial program in Java
Order of a recursive function in C
printing recursive call parameter in C++
Recursive Insertion on Linked Lists in C++
need Recursion help in C

coveredinflies

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

32 posts
since Jul 2008

Permalink

Aug 15th, 2008

Re: Recursive Factorial

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

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.

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Aug 15th, 2008

Re: Recursive Factorial

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

).
How about:

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.

ArkM

Reputation Points: 1234

Solved Threads: 347

Postaholic

Offline

2,001 posts
since Jul 2008

Permalink

Aug 15th, 2008

Re: Recursive Factorial

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

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;
}

scream2ice

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

33 posts
since Mar 2008

Permalink

Aug 15th, 2008

Re: Recursive Factorial

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:

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.

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.

ArkM

Reputation Points: 1234

Solved Threads: 347

Postaholic

Offline

2,001 posts
since Jul 2008

Permalink

Aug 16th, 2008

Re: Recursive Factorial

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

scream2ice

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

33 posts
since Mar 2008

Permalink

Aug 16th, 2008

Re: Recursive Factorial

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!

coveredinflies

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

32 posts
since Jul 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Char* to int or int*

Next Thread in C++ Forum Timeline: pls help palindrome

DaniWeb Message

Cancel Changes

User Name
Password