Computer Science Canada Benefits of recursion |
| Author: | Insectoid [ Thu Mar 03, 2011 7:45 pm ] |
| Post subject: | Benefits of recursion |
So, the general consensus in my programming class is that recursion is bad and iteration is always better. This is a university course for CS students. I love recursion and am one of the few who willingly applies recursion to assignments even where the teacher does not require it. I find it hard to believe that if recursion would be taught in school if it wasn't extremely useful in some cases. However, I find my knowledge of the subject quite restrictive and I haven't got many examples where recursion trumps iteration with which to argue my case. So, I'll leave it up to compsci.ca to decide. My points: -If you're comfortable with recursion, it becomes very easy to write far more legible and condensed code than the iterative counterpart. -Optimzed tail-recursion is nearly as efficient (possibly as efficient, or more) as iteration -Looping in some (or all- I dunno) languages is implemented via recursion- so an iterative function uses recursion anyway (I don't remember where I heard this and don't have a reference, so correct me if I'm wrong). A lot of people are introduced to recursion via the fibonacci sequence, which certainly benefits from an iterative approach(though a bottom-up recursive approach might be very efficient for calculating a list of fibonacci numbers instead of just a single one). This gives students a nasty first impression and may be why so many students think it's awful. I'd love to read compsci.ca's side of it. |
|
| Author: | A.J [ Thu Mar 03, 2011 7:51 pm ] |
| Post subject: | RE:Benefits of recursion |
The concept of recursion is one that definitely needs to be learned by anyone who aspires to be programmer. This is not solely due to the problem solving aspect of it, but mainly to develop the understanding and the logic to understand this topic. This concept of splitting up a problem into smaller subproblems of a similar nature is useful in many scenarios. True, there are cases where iteration is less costly efficiency wise, though there also are cases were recursion is unavoidable (for example when you want to make your code compact, or even in certain problems where there's simply too much information to store iteratively). I believe recursion is a concept that must be taught in high school, and tested throughout high school. |
|
| Author: | Tony [ Thu Mar 03, 2011 8:05 pm ] |
| Post subject: | RE:Benefits of recursion |
Recursion is just a special case of a function call. Most kids don't have a problem with the concept of function A() using a result from function B(), but as soon as B()'s implementation happens to be the same as A()'s, the brains start to melt. Recursion makes a lot of things easy to implement. A lot of concepts in math are defined recursively. Anything that's provable by Mathematical Induction. All of that is trivially translated into working code. Sometimes (a lot of the time!) fast implementation and easy maintenance is more important than optimal execution speed. As AJ points out, it allows you to think of problems in a different way, and solve complicated problems by breaking it down bit by bit. For a complicated problem, I need to figure out only two things: 1) how to take a step towards a slightly less complicated problem (often this comes in a form of "well I don't know how to solve a string of size N, but lets assume that I have a function that returns the answer for N-1... now it's easy"), and 2) trivial base-case solution ("any string of size 0 or 1 is trivial"). This solves a large class of problems you might encounter. Tree traversals are trivial with recursion. This is also essential to a large class of possible problems. Etc. |
|