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

In plain English: Assume you can do 3 things:

1. Take one apple
2. Write down tally marks
3. Count tally marks

You have a lot of apples in front of you on a table and you want to know how many apples there are.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

The process of repeating the same thing till you are done is called recursion.

I hope this is the "plain english" answer you are looking for!

Answer 2

Any algorithm exhibits structural recursion on a datatype if basically consists of a switch-statement with a case for each case of the datatype.

for example, when you are working on a type

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

a structural recursive algorithm would have the form

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

this is really the most obvious way to write any algorith that works on a data structure.

now, when you look at the integers (well, the natural numbers) as defined using the Peano axioms

 integer = 0 | succ(integer)

you see that a structural recursive algorithm on integers looks like this

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

the too-well-known factorial function is about the most trivial example of this form.

Answer 3

Consider an old, well known problem:

In mathematics, the greatest common divisor (gcd) … of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

The definition of gcd is surprisingly simple:

where mod is the modulo operator (that is, the remainder after integer division).

In English, this definition says the greatest common divisor of any number and zero is that number, and the greatest common divisor of two numbers m and n is the greatest common divisor of n and the remainder after dividing m by n.

If you'd like to know why this works, see the Wikipedia article on the Euclidean algorithm.

Let's compute gcd(10, 8) as an example. Each step is equal to the one just before it:

1. gcd(10, 8)
2. gcd(10, 10 mod 8)
3. gcd(8, 2)
4. gcd(8, 8 mod 2)
5. gcd(2, 0)
6. 2

In the first step, 8 does not equal zero, so the second part of the definition applies. 10 mod 8 = 2 because 8 goes into 10 once with a remainder of 2. At step 3, the second part applies again, but this time 8 mod 2 = 0 because 2 divides 8 with no remainder. At step 5, the second argument is 0, so the answer is 2.

Did you notice that gcd appears on both the left and right sides of the equals sign? A mathematician would say this definition is recursive because the expression you're defining recurs inside its definition.

Recursive definitions tend to be elegant. For example, a recursive definition for the sum of a list is

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

where head is the first element in a list and tail is the rest of the list. Note that sum recurs inside its definition at the end.

Maybe you'd prefer the maximum value in a list instead:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

You might define multiplication of non-negative integers recursively to turn it into a series of additions:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

If that bit about transforming multiplication into a series of additions doesn't make sense, try expanding a few simple examples to see how it works.

Merge sort has a lovely recursive definition:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Recursive definitions are all around if you know what to look for. Notice how all of these definitions have very simple base cases, e.g., gcd(m, 0) = m. The recursive cases whittle away at the problem to get down to the easy answers.

With this understanding, you can now appreciate the other algorithms in Wikipedia's article on recursion!

Answer 4

A recursive function is one which calls itself. The most common reason I've found to use it is traversing a tree structure. For example, if I have a TreeView with checkboxes (think installation of a new program, "choose features to install" page), I might want a "check all" button which would be something like this (pseudocode):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

So you can see that the checkRecursively first checks the node which it is passed, then calls itself for each of that node's children.

You do need to be a bit careful with recursion. If you get into an infinite recursive loop, you will get a Stack Overflow exception :)

I can't think of a reason why people shouldn't use it, when appropriate. It is useful in some circumstances, and not in others.

I think that because it's an interesting technique, some coders perhaps end up using it more often than they should, without real justification. This has given recursion a bad name in some circles.

Answer 5

Well, that's a pretty decent definition you have. And wikipedia has a good definition too. So I'll add another (probably worse) definition for you.

When people refer to "recursion", they're usually talking about a function they've written which calls itself repeatedly until it is done with its work. Recursion can be helpful when traversing hierarchies in data structures.

Answer 6

A recursive statement is one in which you define the process of what to do next as a combination of the inputs and what you have already done.

For example, take factorial:

factorial(6) = 6*5*4*3*2*1

But it's easy to see factorial(6) also is:

6 * factorial(5) = 6*(5*4*3*2*1).

So generally:

factorial(n) = n*factorial(n-1)

Of course, the tricky thing about recursion is that if you want to define things in terms of what you have already done, there needs to be some place to start.

In this example, we just make a special case by defining factorial(1) = 1.

Now we see it from the bottom up:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Since we defined factorial(1) = 1, we reach the "bottom".

Generally speaking, recursive procedures have two parts:

1) The recursive part, which defines some procedure in terms of new inputs combined with what you've "already done" via the same procedure. (i.e. factorial(n) = n*factorial(n-1))

2) A base part, which makes sure that the process doesn't repeat forever by giving it some place to start (i.e. factorial(1) = 1)

It can be a bit confusing to get your head around at first, but just look at a bunch of examples and it should all come together. If you want a much deeper understanding of the concept, study mathematical induction. Also, be aware that some languages optimize for recursive calls while others do not. It's pretty easy to make insanely slow recursive functions if you're not careful, but there are also techniques to make them performant in most cases.

Hope this helps...