C++ Programmer Defined Factorial Function

[Saladsamurai]

Hi

I am relatively new to C++ and I am having a little trouble understanding, in detail, the logic
of this recursive function.

Can someone tell me if my reasoning this out is correct?

int fact (int n)
{
	if (n==1)
	return 1;
	 
	else
	return (n*fact(n-1));
	
}

So if the user enters 1, it returns 1. But if the user enters 3... what happens here?

it returns 3*fact(2)
and then fact(2) returns 2*fact(1)
and fact (1)=1
so we have 3*2*1= 3!

okay...so I guess I do get it kind of.

But when it says "return (n*fact(n-1)" where exactly is it "returning" it?

It seems like it means "return it to the argument of the function".

Is that more or less correct? Especially what is in boldface...

 

[rootX]

It's a http://en.wikipedia.org/wiki/Recursion#Recursion_in_computer_science". Not C++ specific thing.

I understood it by assuming that
"int fact (int n)" is not equal to "fact(n-1)" i.e. they are two different functions something like

int fact1 (int n)
{
return fact2(n-1);
}

int fact2 (int n)
{
return something;
}To function or method, there is no difference between calling itself or calling another function..I would say in that line it just calling itself and places the call on the stack.
In 3 case, it keeps on putting calls on the stack until you return 1:
func(1) = 1
func(2)
func(3)

func(1) is evaluated which was called by func(2) and is removed from the stack, then func(2) and then func(3)

 

[Saladsamurai]

It's a recursive function. Not C++ specific thing.

Agreed.

I understood it by assuming that
"int fact (int n)" is not equal to "fact(n-1)" i.e. they are two different functions something like

int fact1 (int n)
{
return fact2(n-1);
}

int fact2 (int n)
{
return something;
}

Not sure about all of that. I think the way I wrote it makes more sense..but that's me!


I guess I just need to know this

when it says "return (n*fact(n-1)" where exactly is it "returning" it?

Is it returning it to n?

 

[Saladsamurai]

noticed your edit. I think that makes some sense to me.

 

[rootX]

when it says "return (n*fact(n-1)" where exactly is it "returning" it?

Is it returning it to n?

You might want to use some better word than returning to n. I don't understand "what "returning to n" is. return (n*fact(n-1)) is just equivalent to return (a constant * fact (n-1))
Whenever fact (n-1) is evaluated and removed from the stack, it returns another constant which is multiplied then by n and then function returns the result.

I don't know anything more about recursion - just that I need a base case (stopping condition) and other body. You can use it instead of for/while loops (in some cases) if your code looks neater but in my understanding, use recursion only if it make your code look simple.

 

[rcgldr]

it returns 3*fact(2)
and then fact(2) returns 2*fact(1)
and fact (1)=1
so we have 3*2*1= 3!

Not quite, the return statement is the value returned when that instance of the function exits. The first return statement, return(3*fact(2)) requires that fact(2) return a value before the expression 3*fact(2) can be evaulated and returned from that instance of the function.The next nested instance of the function has a return statement, return(2*fact(1), and requires fact(1) return a value before it can evaluate the expression and return that value ...

So this sequence unfolded is:

     i = fact(3)
         call fact(2)
               call fact(1)
                   fact(1) returns a 1
               fact(2) returns (2*1)
         fact3 returns(3*2)
     i = 6

 

[Hurkyl]

where exactly is it "returning" it?

To the place where the function is called.

If x is an expression of type int, then fact(x) is also an expression of type int. The value of fact(x) is the value that was returned.

e.g., if the expression x has the value 7, then the value of fact(x) is the value of the expression 7 * fact(6).

 

[Saladsamurai]

Okay.
So fact (3) tries to return an int value. But since it is returning 3*(fact(2))
fact (2) to has to be evaluated first... and so on.

 

[arboretum]

but in my understanding, use recursion only if it make your code look simple.

I was under the impression that recursion carries serious performance penalties, so one should avoid it whenever possible even at the expense of code clarity. Perhaps outside of scientific computing this would be less of an issue, and I'm fairly sure that if you're using something like Lisp, recursive functions are perfectly acceptable.

 

[csprof2000]

"I'm fairly sure that if you're using something like Lisp, recursive functions are perfectly acceptable."

I would hope so.

Recursion is perfectly fine, and don't let anybody tell you differently. Yes, it isn't as efficient as looping. This is, of course, an immediate consequence of the underlying hardware's implementation. It needn't have been such, and may not always be.

Next, it is always possible to make a recursive function iterative, and vice versa. You never "need" to use recursion.

You really should know how both recursion and iteration work.

 

[rcgldr]

I was under the impression that recursion carries serious performance penalties

It comsumes stack space, but with GB's of memory and a large stack size specified, it shouldn't be an issue.

 

[Hurkyl]

For quick functions, I believe the main problem with recursion is that it can't be inlined -- the computer spends more time doing the setup/cleanup for function calls than it does actually performing the calculation, and there is no opportunity for reusing registers or extracting constant subexpressions. There might even be an additional penalty when it gets the branch prediction wrong on the final iteration.

Of course, a good compiler will automatically convert some forms of recursion into loops.

 

[rootX]

I was under the impression that recursion carries serious performance penalties, so one should avoid it whenever possible even at the expense of code clarity. Perhaps outside of scientific computing this would be less of an issue, and I'm fairly sure that if you're using something like Lisp, recursive functions are perfectly acceptable.

Depends what's important to you..

- performance
- readability

 

[csprof2000]

Alright, fine.

Implemented both in C++.
Running each 100,000,000 times for integers 0-9. Integer function.
Timing them, in seconds.

Iterative solution:
45 seconds.

Recursive solution:
168 seconds.

I'm actually sort of impressed by the difference. Here's the code I used:


int factorial_it(int n)
{
int result = 1;

for(int i = 2; i <= n; i++)
result *= i;

return result;
}

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

int main()
{

int t1, t2;

t1 = (int)time(NULL);
for(int n = 0; n < 100000000; n++)
{
for(int i = 0; i < 10; i++)
{
//int tmp = factorial_it(i);
int tmp = factorial_rc(i);
}
}
t2 = (int)time(NULL);

cout << "Elapsed time: " << t2-t1 << endl;


return 0;
}

 

[Hurkyl]

What compiler / optimization settings? (/ architecture)

I tried your code using MSVC++ 2008, both under DEBUG and RELEASE builds, and my results were:

DEBUG: 50 and 158 (similar to what you got)
RELEASE: 7 and 15


I'm somewhat dissapointed that MSVC++ didn't turn the recursive function into a loop. Maybe compilers don't do that optimization, despite what I had learned?

 

[csprof2000]

Well, strictly speaking, the way I wrote the factorial_rc function, it's not tail recursive. That's sort of the point... I believe you'll agree the multiplication, not the recursive call, is the "last" operation being done. I don't think compilers are written to do this optimization since, well, where would you stop it?

I used the V.S. c++ thing at some sort of dingy lab I happened to be at when I did it. I didn't specify any compiler settings, and I was running under debug (almost certainly). As you can probably tell, I wasn't being too careful about it.