Winston Posted September 25, 2004 Share Posted September 25, 2004 Hey i was wondering for the experienced ones, what tips have you got, when to implement recursion and how do go about thinking simply and how do you know when to implement it. Thanks Link to comment Share on other sites More sharing options...
0 neowin_hipster Posted September 25, 2004 Share Posted September 25, 2004 that's a tough one to describe. Think of a binary search. You can divide the task into smaller and smaller parts or versions of itself. Think of the towers of hanoi. The solution is to solve it for a n-1 number of blocks. A classic example is traversing a binary tree (a tree with a left and right subtree). To traverse (one particular ordering) is to visit the left and then the right subtree. of course if the recursion gets too deep you'll want ot make an iterative version to avoid an ever growing stack... Link to comment Share on other sites More sharing options...
0 +chorpeac MVC Posted September 25, 2004 MVC Share Posted September 25, 2004 that's a tough one to describe. Think of a binary search. You can divide the task into smaller and smaller parts or versions of itself. Think of the towers of hanoi. The solution is to solve it for a n-1 number of blocks. A classic example is traversing a binary tree (a tree with a left and right subtree). To traverse (one particular ordering) is to visit the left and then the right subtree.of course if the recursion gets too deep you'll want ot make an iterative version to avoid an ever growing stack... that's a really good description... (Y) Link to comment Share on other sites More sharing options...
0 amoeba Posted September 25, 2004 Share Posted September 25, 2004 Yeah, Goalie explained much of recursion's use. I dunno, I'm tired and can't think of anything special to add. Do you understand what recursion does w/ stack frames and such when it runs? Link to comment Share on other sites More sharing options...
0 neowin_hipster Posted September 25, 2004 Share Posted September 25, 2004 More importantly, what the hell happens to a "forced" inline function if you make it recursive. Any one care to try? Hmm, maybe i will.... with gcc. I wonder what .Net does... Most importantly recursion is used because it is mostly easier to visualize, and its sometimes faster, but like i said before, if you can turn it into a for loop or something, then you're much better off in many cases. Link to comment Share on other sites More sharing options...
0 darkmark327 Posted September 25, 2004 Share Posted September 25, 2004 if you can turn it into a for loop or something, then you're much better off in many cases. iteration is almost always faster than recursion also something to keep in mind is that recursion will often require a helper function, unless the original has the correct parameters Link to comment Share on other sites More sharing options...
0 Winston Posted September 25, 2004 Author Share Posted September 25, 2004 Yeah, Goalie explained much of recursion's use. I dunno, I'm tired and can't think of anything special to add.Do you understand what recursion does w/ stack frames and such when it runs? Hmmm can you explain to me about stack frames :)... i'm only guessing but does the stack actually keep record of every time the functions invoked? And until the function has been completed then it's removed from the stack? I mean if that's the case wouldn't it be difficult to measure when to use recursion i mean surely a recursive function call will terminate on some condition however if this recursive call was implemented on large sets of data, wouldnt you eventually get a stack overflow? Like if your implementation was fine and it worked on reasonable sized data sets however wasn't too fine for large sets, then wouldn't recursion be bad? and thanks Goalie, but when it comes to implementing recursion, i get a bit of a trouble getting my head around it. Anyone else want to add on their experience or nifty tips and tricks? Thanks guys. Link to comment Share on other sites More sharing options...
0 Andareed Posted September 25, 2004 Share Posted September 25, 2004 Usually if you get a stack overflow while writing a recursive function it is a programming/logic error. If you are worried about the internal stack, it is always possible to use stack based in memory. In this case, you are not calling any function recursively; you simply push parameters onto the stack, and pop them when needed. I imagine that most recursive algorithms have an iterative solution, as most (all?) mathematical recursive functions have a non-recursive equivalent. Link to comment Share on other sites More sharing options...
0 Kestrel Posted September 25, 2004 Share Posted September 25, 2004 Any recursive solution has an equivalent iterative solution (there is a proof for this - if you're interested, dig it up yourself). The whole recursion versus iteration argument is something you have to decide for yourself based on programme resources, the data-sets involved, the task involved and the algorithms you plan on using. The beauty of recursion is that it is self-describing for many algorithms and so makes the code that much more intuitive. That's not to say that iteration can not be concise - it certainly can, but a recursive solution is often cleaner to look at. Compare the code for something like Fibonacci sequences or Quicksorts and the recursive solution will often be cleaner... of course, you pay for that brevity with machine resources as your stack depth grows. If you're truly interested in the concepts of iterative versus recursive solutions, check out game theory - many games can be described as a tree of possible states and there are a great many discussions on when to generate states iteratively and when to generate recursively. Link to comment Share on other sites More sharing options...
0 neowin_hipster Posted September 25, 2004 Share Posted September 25, 2004 What happens when you call a function requires a bit of compiler knowledge and a bit of assembly knowledge, needless to say the bare minimum required usually involves at least a return address pushed onto the stack, but often local variables, and passed and returned variables are thrown on the stack. Registers are usually saved to the stack as well. I hope i didn't forget anything, but you get the picture. The stack can grow like a monster so if your recursion gets too deep it can grow like crazy... Link to comment Share on other sites More sharing options...
0 Winston Posted September 26, 2004 Author Share Posted September 26, 2004 What happens when you call a function requires a bit of compiler knowledge and a bit of assembly knowledge, needless to say the bare minimum required usually involves at least a return address pushed onto the stack, but often local variables, and passed and returned variables are thrown on the stack. Registers are usually saved to the stack as well. I hope i didn't forget anything, but you get the picture. The stack can grow like a monster so if your recursion gets too deep it can grow like crazy... Yeah i realised that idea, i mean then what happens if say, my particular method was designed to cater well for small data sets, however under large data sets the the extent in which recusive calls have been done, wouldn't it have a high possibility in which a stack overflow might occur? Link to comment Share on other sites More sharing options...
0 Andareed Posted September 26, 2004 Share Posted September 26, 2004 Stack overflow is not very likely. Consider a binary tree (tree with at most 2 children). Suppose you have 4 billion nodes in your tree. You tree height will be 32. Any recursive algorithm on such a tree would call your function at most 32 times in a row. That is, your stack would contain only 32 frames. Depending on the system, you could have hundred's of frames on the stack without overflow. You could then safely process 2^100 (how many atoms are in the known universe?) pieces of data. Link to comment Share on other sites More sharing options...
0 Winston Posted September 26, 2004 Author Share Posted September 26, 2004 Stack overflow is not very likely. Consider a binary tree (tree with at most 2 children). Suppose you have 4 billion nodes in your tree. You tree height will be 32. Any recursive algorithm on such a tree would call your function at most 32 times in a row. That is, your stack would contain only 32 frames. Depending on the system, you could have hundred's of frames on the stack without overflow. You could then safely process 2^100 (how many atoms are in the known universe?) pieces of data. Well yeah, but if you take into account of the rest of your application using stack memory, wouldn't there be a chance that this stack memory usage + the recusive calls, cause an overflow? And just a sort of off topic question, is the stack size always set and defined? Like for C++, is it self resized and managed, as opposed to managed code would that be a set size by the compiler? Link to comment Share on other sites More sharing options...
0 darkmark327 Posted September 26, 2004 Share Posted September 26, 2004 Stack overflow is not very likely. Consider a binary tree (tree with at most 2 children). Suppose you have 4 billion nodes in your tree. You tree height will be 32. Any recursive algorithm on such a tree would call your function at most 32 times in a row. That is, your stack would contain only 32 frames. Depending on the system, you could have hundred's of frames on the stack without overflow. You could then safely process 2^100 (how many atoms are in the known universe?) pieces of data. I think everyone's doing too much bombarding him with stack frames and everything instead of just helping him use recursion first. I really don't think he's going to be doing anything wherein he has to worry about running of stack pages for a while. Of course I am not talking about the inevitable "infinite recursion blunders" Anyway consider a function that deletes all files in a directory. if it's a file you'll want to delete it if it's a directory, you'll want to go into it and delete its files. You should start to see where I'm going with this. so if it's a directory, we'll call that function again on that directory (from inside that function!). Once that directory has been cleaned out, then we can continue with the rest of the current directory. So for example void deleteAll(directory folderToDelete) { //iterate through all files in directory foreach(file fileToDelete in folderToDelete) { if(fileToDelete.isDirectory()) deleteAll(fileToDelete); delete(fileToDelete); } } Link to comment Share on other sites More sharing options...
0 darkmark327 Posted September 26, 2004 Share Posted September 26, 2004 Well yeah, but if you take into account of the rest of your application using stack memory, wouldn't there be a chance that this stack memory usage + the recusive calls, cause an overflow? And just a sort of off topic question, is the stack size always set and defined? Like for C++, is it self resized and managed, as opposed to managed code would that be a set size by the compiler? There is always a chance. I'm pretty sure the stack is set up by the kernel so that'd be set by the OS. It wouldn't need to be resized, just filled, and when emptied the data would still be there, but it'd just be marked to be overwritten. Link to comment Share on other sites More sharing options...
0 Winston Posted September 26, 2004 Author Share Posted September 26, 2004 There is always a chance. I'm pretty sure the stack is set up by the kernel so that'd be set by the OS. It wouldn't need to be resized, just filled, and when emptied the data would still be there, but it'd just be marked to be overwritten. wow thanks for your help, ok i'm gonna read your longish post haha... just a question, what's so different about the stack as opposed to the heap, like what's done to the stack to make it better ? Link to comment Share on other sites More sharing options...
0 amoeba Posted September 26, 2004 Share Posted September 26, 2004 Well, the stack data type is a special data type (abstract data type). It basically has two main functions: push and pop. Push is supposed to toss something on top (visually speaking) of the stack and pop takes something off. It's like a stack of plates. You get to them from the top, and add from the top. The idea with recursion is to take advantage of this super-simple way of dealing with data. In my experience, recursion is used to get to the end of something, a list, whatever (directory tree example before was great). Once you get to the end of your looping (often a while loop), the while loop no longer executes and something is executed for each stack frame as you slowly work your way down the stack (of plates? :) ). In the directory case given earlier in this thread, you'd be deleting on condition (if is file). I dont know if what I said made any sense. Recursion seems like it can be less code but harder to figure out (at least for me) and not always as effecient. I stay away from recursion as it takes smart people to write good recursion :) Oh, and said above was that sometimes recursion requires a helper function. It might sometimes but having a helper function means the recursion isn't all that slick anyways. Recursion should stay pretty simple and doing magic stuff with helper functions just takes away from the elegance that is recursion. Blah! :p Link to comment Share on other sites More sharing options...
0 Oogle Posted September 27, 2004 Share Posted September 27, 2004 There is always a chance. I'm pretty sure the stack is set up by the kernel so that'd be set by the OS... Each program's stack size (in Windows) can be configured through the compiler that created it. Just fiddle with your linker settings. Of course, making your stack size large eats up more memory. Link to comment Share on other sites More sharing options...
Question
Winston
Hey i was wondering for the experienced ones, what tips have you got, when to implement recursion and how do go about thinking simply and how do you know when to implement it.
Thanks
Link to comment
Share on other sites
17 answers to this question
Recommended Posts