Recursion... why?

After reading the chapter on Recursion in my book, it posed a very interesting statement:

Quote:

---

Recursion has many negatives. It repeatedly invokes the mechanism, and consequently the overhead, of function calls. This can be both expensive in both processor time and memory space. Each recursive call causes another copy of the function variables to be created, this can comsume considerable memory.

Iteration normally occurs within the function, so the overhead of repeated function calls and extra memory assignment is omited.

So, why choose recursion?

---

I understand it is all about choosing the right style for the job in hand, so why teach me somthing when it is deemed as bad to do? Im interested to know if what they have told me is somthing I need to look at, and avoid recursion in my programs.

Some problems are more naturally solved with recursion (though this may depend on the coder).

For example quicksort:

Code:

---

def quicksort(range):
    lower, upper = partition(range)
    if lower:
          quicksort(lower)
    if upper:
          quicksort(higher)

---

Recursion is convenient because it manages the stack of ranges to sort for you.

On the other hand, there probably isn't much point to using recursion for things which might be more simply done with a loop (e.g calculating factorial - since there is no stack to maintain).

Recursion should be avoided except in a few broadly applicable cases:
1)When the number of iterations is consistently small and recursion appears to describe the solution susinctly.
2)When writing an algorithm to work without recursion would be unduly complex, and result in hard to follow code.
3)When the algorithm is naturally recursive, such that all local variables are necessary to copy into a stack anyway, and the function overhead therefore countered by equivalent iterative measures.

So in general, you should avoid recursion. But there are cases where recursion offers simpler solutions, so its something to keep in mind.

Recursion is one tool that can be a choice for certain types of problems, as explained above.

Knowing when and where to use which tool is part of learning to program. Part of that is of course understanding the consequences of the choice of a particular method or tool. If you have a heavy, big hammer, it will get nails into a piece of wood very easily. But if you have small panel tacks (little nails, less than 2cm long), then a 5lbs sledge-hammer is not the right choice. On the other hand, when you want to take down a wall, a 5+lbs hammer is exactly what you want/need (and the tiny one that is suitable for the little nails will NOT work).

--
Mats

Quote:

---

Originally Posted by swgh

I understand it is all about choosing the right style for the job in hand, so why teach me somthing when it is deemed as bad to do? Im interested to know if what they have told me is somthing I need to look at, and avoid recursion in my programs.

---

It's really a language-specific question. Most functional languages have no loops, which means everything is recursion. The question to pose yourself is "Should I use recursion for this task when I'm programming in C/C++?" EDIT: Point being, in many languages you have no choice whether to use recursion. So the rule "Avoid it unless impossible" is really too general. From a CS standpoint, recursion is a better description of problems than iteration. If we lived in a perfect world (infinitely fast machines, infinite memory), then recursion would always be preferable, hands down.

There are data structures (e.g. trees) which are recursive, and the algorithms which process these data structures are recursive as well. It's usually possible to "unwrap" recursion into plain iteration, but the code often becomes more confusing. Is it worth the additional complexity in return for performance? Sometimes it is, sometimes not. And if the recursive structures are amazingly deep, you can run out of stack space if you try to process them recursively.

It takes experience.