• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
wicked357

Factorial Recursion

14 posts in this topic

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.
0

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
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 [url="http://en.wikipedia.org/wiki/Memoization"]memoize[/url], 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.
[code]#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';
}
[/code]

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:
[code]#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';
}
[/code]

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.
2

Share this post


Link to post
Share on other sites
[quote name='wicked357' timestamp='1328146290' post='4908573']
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.
[/quote]

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! [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

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.
2

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1328641169' post='4910593']
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.
[/quote]
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
[quote name='SiCrane' timestamp='1328643339' post='4910605']
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.
[/quote]
Regardless, though -- I think it's a bad idea to implement anything recursively that could even [i]potentially[/i] 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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
[quote name='taz0010' timestamp='1328792737' post='4911280']
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.[/quote]

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.
0

Share this post


Link to post
Share on other sites
[quote name='Antheus' timestamp='1328801553' post='4911332']
QuickSort grows by n^2.
[/quote]

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

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1328814268' post='4911398']
[quote name='Antheus' timestamp='1328801553' post='4911332']
QuickSort grows by n^2.
[/quote]

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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0