Factorial Recursion

THe most common issue with recursion is stack overflow in languages or compilers that don't support tail recursion.

Other than that, sometimes it's faster to use an iterative approach.

In the particular case of the factorial function, you'll run into the limits of your number type way before you hit the buffer overflow.

To complement what Washu said, recursive functions are sometimes more clear than iterative ones, and they are also easy to memoize, leading to a very readable implementation of dynamic programming for some problems.

For instance, the following C++ program computes how many ways you can make 1 dollar (100 cents) using coins of 1 cent, 5 cents, 10 cents, 25 cents, 50 cents and 1 dollar.
#include <iostream>

int coin_types[] = {1,5,10,25,50,100};

int make_change(int n, int max_coin_type) {
if (max_coin_type == 0)
return 1; // only 1 way to make any number of cents if you only use 1-cent coins

int result = 0;
for (; n >= 0; n-=coin_types[max_coin_type])
result += make_change(n, max_coin_type-1);

return result;
}

int main() {
std::cout << make_change(100,5) << '\n';
}


This algorithm is pretty clean (I think), but it takes time O(n^k), k being the number of coin types (6). If we use some memory to remember past results, the algorithm becomes dynamic programming, with a much better performance of O(k*n). So, for instance, you can compute how many ways you can make change of 20 dollars using those same coins denominations:
#include <iostream>

int coin_types[] = {1,5,10,25,50,100};

int make_change(int n, int max_coin_type) {
int const memory_size = 2001;
static int memory[6][memory_size] = {0};

if (max_coin_type == 0)
return 1; // only 1 way to make any number of cents if you only use 1-cent coins

if (n < memory_size && memory[max_coin_type][n] > 0)
return memory[max_coin_type][n]; // I remember this one!

int result = 0;
for (; n >= 0; n-=coin_types[max_coin_type])
result += make_change(n, max_coin_type-1);

if (n < memory_size)
memory[max_coin_type][n] = result; // let's remember the result

return result;
}

int main() {
std::cout << make_change(2000,5) << '\n';
}


Of course, this can be implemented without recursion, but I think the code would be less readable. There are other algorithms that are even less amenable to being written without recursion. The best example of this is alphabeta search, which is used for the AI in games like chess.

I am curious I was asked a question today that just irks me cause I didn't know the answer and I blanked out. Here is a sample code that I wrote to show you. There are tons of examples on it anyways I just can't seem to find the answer.

[source]
function factorial($factor)
{
$temp;
if ($factor <= 1)
return 1;
return $temp = $factor * factorial($factor - 1);
}
// Example use

echo factorial(3);
[/source]

Doesn't really matter what language as long as it allows you to call the function in its function.

Anyways the question was what is the advantage and disadvantage of using this... I froze so bad! Anyone able to explain this to me there was no over the other. I can write it in a different language if you don't understand it, but I am sure that won't be the issue. Thanks in advance.

There are times when recursion makes a lot of sense and can give you an elegant algorithm. Namely when the problem at hand is nothing more than a series of extremely similar sub-problems. Printing out a binary tree in sorted order looks way better in recursive form than the equivalent iterative solution (Python code):

[source]

#recursive
def print_binary_tree(tree):
if tree.left != None:
print_binary_tree(tree.left)
print tree.value
if tree.right != None:
print_binary_tree(tree.right)

#iterative
def print_binary_tree(tree):
tree_stack = []
while len(tree_stack) > 0 or tree != None:
if tree != None:
tree_stack.append(tree)
tree = tree.left
else:
tree = tree_stack.pop()
print tree.value
tree = tree.right
[/source]


NOTE: don't hate if there are minor issues with either of these functions, I haven't tested them!

The recursive solution is far easier to understand (imo) than the iterative solution. The recursive solution implicitly takes care of the stack state for us, while the iterative solution has to implement it's own stack in order to operate in the same way. That makes the recursive solution much more elegant, but it's not without it's drawbacks. As Washu mentioned, compilers tend to optimize out recursive functions with "tail call optimization" -- which means that if the recursive call to the same function is the last expression in the function, the compiler can turn it into an iterative form behind the scenes and do away with a stack overflow from occurring for monstrous recursive call chains. In the above implementation we have two recursive calls and that is problematic: if the tree is big enough, our "print_binary_tree(tree.left)" call will dig deep into the tree will take up a lot of memory on the stack before it hits an exit condition.

Some languages impose a hard limit on the amount of non-tail optimized recursive calls you can do: I believe Python will stop you after your stack depth gets a couple thousand calls deep. Other languages that are less safe like C++ will let you go on until you receive a stack overflow exception. Some compiled languages will even give you a warning when they detect that a recursive method is not optimized for tail call recursion.

At that point you have a few choices: you can rewrite your recursive function to utilize tail call optimization by making the only recursive call the last expression in the function, or you can just scrap it and rewrite it iteratively. The iterative solution can maintain it's stack in a memory space (such as the heap) that can grow much larger as needed. Rewriting the above recursive print_binary_tree function to utilize tail call optimization would look like this:

[source]


#recursive with dynamic programming
def print_binary_tree(tree, tree_stack=[]):
if tree != None:
tree_stack.append(tree)
tree = tree.left
elif len(tree_stack) > 0:
tree = tree_stack.pop()
print tree.value
tree = tree.right
else:
return
print_binary_tree(tree, tree_stack)

[/source]

It does basically what the iterative solution does, except without the while loop. I think it's a bit prettier than the iterative solution, but the difference is negligible.

What you choose to do will depend entirely on the problem at hand, the trade off you need between elegance and performance, and the amount of data you are processing. Iterative solutions will generally perform a little faster as they scale up because there is less overhead from stack manipulation and function calls. Recursive solutions, depending on the problem, can often times be much more readable and understandable.

In that case I would say:

Pros: Easy to follow and read. Although so is an iterative version.

Cons: Could cause stack overflow, iterative method is much better in this case and is probably faster.

Recursion is elegant and algorithms with natural recursive structure look nice when implemented recursively.

However, in C++ one should be wary of using recursion because it is fundamentally unsafe. The issue is is that in C++ there is basically no way to handle or even detect, really, the situation in which you are deep in a recursive call and run out of stack space. That is other than, (a) formally proving or otherwise convincing co-workers that the recursive algorithm in question is guaranteed to terminate never using more than k stack frames, (b) keeping track of the depth of recursion and arbitrarily bailing out at some depth k, or (c) doing some non-portable platform dependent hack to detect stack overflows.

So some people never use recursion in production code. Personally I think that's going a little far.

I had never heard of people being so paranoid about lack of ability to detect stack overflow. In practice, I believe it's not much easier to handle out-of-memory problems, and most programs don't deal gracefully with full file systems either.

I had never heard of people being so paranoid about lack of ability to detect stack overflow. In practice, I believe it's not much easier to handle out-of-memory problems, and most programs don't deal gracefully with full file systems either.

I have seen it. Like I said, I think it's going too far.

But to play devil's advocate, out-of-memory and full file systems really are a different situation. I mean, no one is talking about recovering from such a situation but if you try to allocate a big block of memory and the allocation fails, you can handle that and throw an exception or whatever. Same thing with trying to write a big file to a full hard drive. However, if you have even a correct recursive algorithm that is, say, growing stack frames exponentially and you blow up the stack, you are going to hard crash.

Not necessarily, some platforms provide the ability to detect a stack overflow. You usually can't do anything useful after one, but you can at least crash semi-gracefully. For example, Windows will raise a EXCEPTION_STACK_OVERFLOW SEH exception, which can be handled.

Not necessarily, some platforms provide the ability to detect a stack overflow. You usually can't do anything useful after one, but you can at least crash semi-gracefully. For example, Windows will raise a EXCEPTION_STACK_OVERFLOW SEH exception, which can be handled.

Regardless, though -- I think it's a bad idea to implement anything recursively that could even potentially overflow the stack. I mean, generally you have some sense of the kind of input a recursive function will be called on and what that will do in terms of stack space and can just make implementation decisions based on that. So say there's some function that takes a vector of n values and then does divide-and-conquer-style recursion so that the maximum stack size will be O(log n). If n could commonly be on the order of hundreds of thousands, would you implement this recursively? -- I wouldn't even though it is probably okay to do so ... that's basically all I'm saying.

For O(log n) worst case, as long as the constant factors weren't gigantic, I'd probably still use recursion. For example, I don't see a reason not to write introsort recursively.

Considering that your average recursive function with a stack growth of log(n) is likely to only overflow some point after the universe reaches maximum entropy, I wouldn't be too worried about it.
And this is only possible with algorithms implemented in a way where the upper bound isn't simply a function of the datatype size. (i.e. 2^32 or 2^64 max values for a comparison sort). Stack size is a compiler option you can control anyhow.

Considering that your average recursive function with a stack growth of log(n) is likely to only overflow some point after the universe reaches maximum entropy, I wouldn't be too worried about it.

QuickSort grows by n^2.

Unless specifically implemented so it doesn't.

You'd be surprised how many recursive algorithms can trivially blow the stack.

Fork/join, the fork part takes an array, then splits it into smaller pieces and hands those off to multiple cores. Algorithm grows by n. Library where I encountered this problem was written by someone who never tested with even moderately-sized array and didn't know about recursion problems. And it blew the stack, obviously only in production, when array had 10,000+ elements (which is tiny). Same problem as QS, but here partition sizes matter, so QS solution isn't directly possible.


Another problem is sufficiently smart compiler. Some compilers may choose to optimize tail recursion into a loop. Others might not. Result is that same code using different compiler/VM will blow stack, while other never will.

Python specifically does not perform such optimization for this very reason. It's one of most commonly requested features which won't be done.


Recursive behavior also carries other hidden cost, same as auto-allocation. If number of visited states is large, temporaries created on each step perform a lot of resource management. Not a problem with fib, but consider a DOM walker or UI toolkit, where kilobytes or even megabytes might be manipulated on each step. Solution here isn't necessarily removal of recursion, but moving resource management out of recursive path.

QuickSort grows by n^2.

I believe you meant O(n). If not, please explain where the n^2 comes from, because I am missing something.

[quote name='Antheus' timestamp='1328801553' post='4911332']
QuickSort grows by n^2.

I believe you meant O(n). If not, please explain where the n^2 comes from, because I am missing something.
[/quote]

Meh, n.

Reason it's worth mentioning is because most textbooks/references use naive partition which suffers from this problem. And despite "only" n, it doesn't take much to overflow the stack.