Recursive Factorial

[coveredinflies]

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

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.

[iamthwee]

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

int factorial ( int number )
{
  int temp;

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

[ArkM]

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

int factorial(int n)
{
    return n <= 1? 1: n*factorial(n-1);
}

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

[scream2ice]

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

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

[ArkM]

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:

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.

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.

[scream2ice]

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

[coveredinflies]

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!