Power of Recursion

[Zivojin]

Hello guys.I am interested is there a point of using recursion for some mathematical problems like factorial or binomial coefficients.I have read somewhere that recursions can lead stack overflow.When is the best and effective way to use recursion? Is recursion the most effective way for factorials for example?

int Factorial(int a)
{
if(a==1)
return a;
else return a*Factorial(a-1);
}

[AbstractionAnon]

I have read somewhere that recursions can lead stack overflow

Yes, that can happen. Whether than happens depends on the size of the stack frame, how many times you recurse and how large a stack the OS and/or machine allows.

Is recursion the most effective way for factorials for example?

I wouldn't solve for factorials using recursion. A loop is just as effective and avoids the possibility of stack overflow. Solving factorials is a classic example for demonstrating recursion.

[dutch]

Recursion is useful when it simplifies a problem without either overflowing the stack or doing too much repetitive work (as with fibonacci numbers).

In C++ if it's easy to code the problem in a non-recursive way, that's usually best. If it's difficult to write it in a non-recursive way, then recursion is probably okay since to remove it would basically require using a stack anyway (although you may be able to use less space with your own stack).

For factorials, since only up to factorial(20) fits into 64 bits it's often best to just use a table. Only up to factorial(12) fits into 32 bits.

[jonnin]

recursion can blow up the stack but the stack on modern computers is quite large. You will not blow it out on anything doing 'normal' math like sequences and series; you would literally have to make many thousands of recursive calls without resolving any of them before it crashed for typical problems. The number of calls varies as the footprint of functions vary, but most of these math type functions have a small stack memory requirement. Each local variable and parameter costs stack space, as does the function itself, if that makes sense, so something with 50 parameters and 50 local variables can make a lot less recursive calls vs one with 2 parameters and 2 locals.

Also, the compiler converts some recursion to a loop for you, which has no impact on the stack at all, because it does not really do recursion but has removed that from the behavior for performance. That is, it looks like recursion in the C++ code but the machine code does not do this activity.

Recursion is a last resort for me. It can yield some small, tight, and attractive code, but it is difficult to debug, edit, and performance tune recursive routines.