What is recursion and when should I use it?

Question

One of the topics that seems to come up regularly on mailing lists and online discussions is the merits (or lack thereof) of doing a Computer Science Degree. An argument that seems to come up time and again for the negative party is that they have been coding for some number of years and they have never used recursion.

So the question is:

1. What is recursion?
2. When would I use recursion?
3. Why don't people use recursion?

Answer 1

hey, sorry if my opinion agrees with someone, I'm just trying to explain recursion in plain english.

suppose you have three managers - Jack, John and Morgan. Jack manages 2 programmers, John - 3, and Morgan - 5. you are going to give every manager 300$ and want to know what would it cost. The answer is obvious - but what if 2 of Morgan-s employees are also managers?

HERE comes the recursion. you start from the top of the hierarchy. the summery cost is 0$. you start with Jack, Then check if he has any managers as employees. if you find any of them are, check if they have any managers as employees and so on. Add 300$ to the summery cost every time you find a manager. when you are finished with Jack, go to John, his employees and then to Morgan.

You'll never know, how much cycles will you go before getting an answer, though you know how many managers you have and how many Budget can you spend.

Recursion is a tree, with branches and leaves, called parents and children respectively. When you use a recursion algorithm, you more or less consciously are building a tree from the data.

Answer 2

Recursion is an expression directly or indirectly referencing itself.

Consider recursive acronyms as a simple example:

• GNU stands for GNU's Not Unix
• PHP stands for PHP: Hypertext Preprocessor
• YAML stands for YAML Ain't Markup Language
• WINE stands for Wine Is Not an Emulator
• VISA stands for Visa International Service Association

More examples on Wikipedia

Answer 3

You want to use it anytime you have a tree structure. It is very useful in reading XML.

Answer 4

In the most basic computer science sense, recursion is a function that calls itself. Say you have a linked list structure:

struct Node {
    Node* next;
};

And you want to find out how long a linked list is you can do this with recursion:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(This could of course be done with a for loop as well, but is useful as an illustration of the concept)

Answer 5

1. A function that calls itself
2. When a function can be (easily) decomposed into a simple operation plus the same function on some smaller portion of the problem. I should say, rather, that this makes it a good candidate for recursion.
3. They do!

The canonical example is the factorial which looks like:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

In general, recursion isn't necessarily fast (function call overhead tends to be high because recursive functions tend to be small, see above) and can suffer from some problems (stack overflow anyone?). Some say they tend to be hard to get 'right' in non-trivial cases but I don't really buy into that. In some situations, recursion makes the most sense and is the most elegant and clear way to write a particular function. It should be noted that some languages favor recursive solutions and optimize them much more (LISP comes to mind).

Answer 6

I like this definition:
In recursion, a routine solves a small part of a problem itself, divides the problem into smaller pieces, and then calls itself to solve each of the smaller pieces.

I also like Steve McConnells discussion of recursion in Code Complete where he criticises the examples used in Computer Science books on Recursion.

Don't use recursion for factorials or Fibonacci numbers

One problem with computer-science textbooks is that they present silly examples of recursion. The typical examples are computing a factorial or computing a Fibonacci sequence. Recursion is a powerful tool, and it's really dumb to use it in either of those cases. If a programmer who worked for me used recursion to compute a factorial, I'd hire someone else.

I thought this was a very interesting point to raise and may be a reason why recursion is often misunderstood.

EDIT: This was not a dig at Dav's answer - I had not seen that reply when I posted this