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

1.) A method is recursive if it can call itself; either directly:

void f() {
   ... f() ... 
}

or indirectly:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) When to use recursion

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) People use recursion only when it is very complex to write iterative code. For example, tree traversal techniques like preorder, postorder can be made both iterative and recursive. But usually we use recursive because of its simplicity.

Answer 2

To recurse on a solved problem: do nothing, you're done.
To recurse on an open problem: do the next step, then recurse on the rest.

Answer 3

A recursive function is a function that contains a call to itself. A recursive struct is a struct that contains an instance of itself. You can combine the two as a recursive class. The key part of a recursive item is that it contains an instance/call of itself.

Consider two mirrors facing each other. We've seen the neat infinity effect they make. Each reflection is an instance of a mirror, which is contained within another instance of a mirror, etc. The mirror containing a reflection of itself is recursion.

A binary search tree is a good programming example of recursion. The structure is recursive with each Node containing 2 instances of a Node. Functions to work on a binary search tree are also recursive.

Answer 4

In plain English, recursion means to repeat someting again and again.

In programming one example is of calling the function within itself .

Look on the following example of calculating factorial of a number:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Answer 5

"If I have a hammer, make everything look like a nail."

Recursion is a problem-solving strategy for huge problems, where at every step just, "turn 2 small things into one bigger thing," each time with the same hammer.

Example

Suppose your desk is covered with a disorganized mess of 1024 papers. How do you make one neat, clean stack of papers from the mess, using recursion?

1. Divide: Spread all the sheets out, so you have just one sheet in each "stack".
2. Conquer:
   2. Go around, putting each sheet on top of one other sheet. You now have stacks of 2.
   3. Go around, putting each 2-stack on top of another 2-stack. You now have stacks of 4.
   4. Go around, putting each 4-stack on top of another 4-stack. You now have stacks of 8.
   5. ... on and on ...
   6. You now have one huge stack of 1024 sheets!

Notice that this is pretty intuitive, aside from counting everything (which isn't strictly necessary). You might not go all the way down to 1-sheet stacks, in reality, but you could and it would still work. The important part is the hammer: With your arms, you can always put one stack on top of the other to make a bigger stack, and it doesn't matter (within reason) how big either stack is.

Answer 6

Whenever a function calls itself, creating a loop, then that's recursion. As with anything there are good uses and bad uses for recursion.

The most simple example is tail recursion where the very last line of the function is a call to itself:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

However, this is a lame, almost pointless example because it can easily be replaced by more efficient iteration. After all, recursion suffers from function call overhead, which in the example above could be substantial compared to the operation inside the function itself.

So the whole reason to do recursion rather than iteration should be to take advantage of the call stack to do some clever stuff. For example, if you call a function multiple times with different parameters inside the same loop then that's a way to accomplish branching. A classic example is the Sierpinski triangle.

You can draw one of those very simply with recursion, where the call stack branches in 3 directions:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

If you attempt to do the same thing with iteration I think you'll find it takes a lot more code to accomplish.

Other common use cases might include traversing hierarchies, e.g. website crawlers, directory comparisons, etc.

Conclusion

In practical terms, recursion makes the most sense whenever you need iterative branching.