In plain English, what is recursion?

Question

The idea of recursion is not very common in real world. So, it seems a bit confusing to the novice programmers. Though, I guess, they become used to the concept gradually. So, what can be a nice explanation for them to grasp the idea easily?

Answer 1

To explain recursion, I use a combination of different explanation, usually to both try to:

• explain the concept,
• explain why it matters,
• explain how to get it.

For starters, Wolfram|Alpha defines it in more simple terms than Wikipedia:

An expression such that each term is generated by repeating a particular mathematical operation.

---

Maths

If your student (or the person you explain too, from now on I'll say student) has at least some mathematical background, they've obviously already encountered recursion by studying series and their notion of recursivity and their recurrence relation.

A very good way to start is then to demonstrate with a series and tell that it's quite simply what recursion is about:

• a mathematical function...
• ... that calls itself to compute a value corresponding to an n-th element...
• ... and which defines some boundaries.

Usually, you either get a "huh huh, whatev'" at best because they still do not use it, or more likely just a very deep snore.

---

Coding Examples

For the rest, it's actually a detailed version of what I presented in the Addendum of my answer for the question you pointed to regarding pointers (bad pun).

At this stage, my students usually know how to print something to the screen. Assuming we are using C, they know how to print a single char using write or printf. They also know about control loops.

I usually resort to a few repetitive and simple programming problems until they get it:

• the factorial operation,
• an alphabet printer,
• a reversed alphabet printer,
• the exponentation operation.

Factorial

Factorial is a very simple math concept to understand, and the implementation is very close to its mathematical representation. However, they might not get it at first.

Alphabets

The alphabet version is interesting to teach them to think about the ordering of their recursive statements. Like with pointers, they will just throw lines randomly at you. The point is to bring them to the realization that a loop can be inverted by either modifying the conditions OR by just inverting the order of the statements in your function. That's where printing the alphabet helps, as it's something visual for them. Simply have them write a function that will print one character for each call, and calls itself recursively to write the next (or previous) one.

^{FP fans, skip the fact that printing stuff to the output stream is a side effect for now... Let's not get too annoying on the FP-front. (But if you use a language with list support, feel free to concatenate to a list at each iteration and just print the final result. But usually I start them with C, which is unfortunately not the best for this sort of problems and concepts).}

Exponentiation

The exponentiation problem is slightly more difficult (at this stage of learning). Obviously the concept is exactly the same as for a factorial and there is no added complexity... except that you have multiple parameters. And that is usually enough to confuse people and throw them off at the beginning.

Its simple form:

can be expressed like this by recurrence:

Harder

Once these simple problems have been shown AND re-implemented in tutorials, you can give slightly more difficult (but very classic) exercises:

• The Fibonacci numbers,
• The Greatest Common Divisor,
• The 8-Queens problem,
• The Towers of Hanoi game,
• And if you have a graphical environment (or can provide code stubs for it or for a terminal output or they can manage that already), things like:
  • Koch's Snow Flake Fractal,
  • Sierpinski's Triangle.
• And for for practical examples, consider writing:
  • a tree traversal algorithm,
  • a simple mathematical expression parser,
  • a minesweeper game.

Note: Again, some of these really aren't any harder... They just approach the problem from exactly the same angle, or a slightly different one. But practice makes perfect.

---

Helpers

A Reference

Some reading never hurts. Well it will at first, and they'll feel even more lost. It's the sort of thing that grows on you and that sits in the back of your head until one day your realize that you finally get it. And then you think back of these stuff you read. The recursion, recursion in Computer Science and recurrence relation pages on Wikipedia would do for now.

Level/Depth

Assuming your students do not have much coding experience, provide code stubs. After the first attempts, give them a printing function that can display the recursion level. Printing the numerical value of the level helps.

The Stack-as-Drawers Diagram

Indenting a printed result (or the level's output) helps as well, as it gives another visual representation of what your program is doing, opening and closing stack contexts like drawers, or folders in a file system explorer.

Recursive Acronyms

If your student is already a bit versed into computer culture, they might already use some projects/softwares with names using recursive acronyms. It's been a tradition going around for some time, especially in GNU projects. Some examples include:

Recursive:

• GNU - "GNU's Not Unix"
• Nagios - "Nagios Ain't Gonna Insist On Sainthood"
• PHP - "PHP Hypertext Preprocessor" (and originall "Personal Home Page")
• Wine - "Wine Is Not an Emulator"
• Zile - "Zile Is Lossy Emacs"

Mutually Recursive:

• HURD - "HIRD of Unix-Replacing Daemons" (where HIRD is "HURD of Interfaces representing Depth")

Have them try to come up with their own.

Similarly, there are many occurrences of recursive humor, like Google's recursive search correction. For more information on recursion, read this answer.

---

Pitfalls and Further Learning

Some issues that people usually struggle with and for which you need to know answers.

Why, oh God Why???

Why would you do that? A good but non-obvious reason is that it is often simpler to express a problem that way. A not-so-good but obvious reason is that it often takes less typing (don't make them feel soooo l33t for just using recursion though...).

Some problems are definitely easier to solve when using a recursive approach. Typically, any problem you can solve using a Divide and Conquer paradigm will fit a multi-branched recursion algorithm.

What's N again??

Why is my n or (whatever your variable's name) different every time? Beginners usually have a problem understanding what a variable and a parameter are, and how to things named n in your program can have different values. So now if this value is in the control loop or recursion, that's even worse! Be nice and do not use the same variable names everywhere, and make it clear that parameters are just variables.

End Conditions

How do I determine my end condition? That's easy, just have them say the steps out loud. For instance for the factorial start from 5, then 4, then ... until 0.

The Devil is in the Details

Do not talk to early abut things like tail call optimization. I know, I know, TCO is nice, but they don't care at first. Give them some time to wrap their heads around the process in a way that works for them. Feel free to shatter their world again later on, but give them a break.

Similarly, don't talk straight from the first lecture about the call stack and its memory consumption and ... well... the stack overflow. I often tutor students privately who show me lectures where they have 50 slides about everything there's to know about recursion when they can barely write a loop correctly at this stage. That's a good example of how a reference will help later but right now just confuses you deeply.

But please, in due time, make it clear that there are reasons to go the iterative or recursive route.

Mutual Recursion

We've seen that functions can be recursive, and even that they can have multiple call points (8-queens, Hanoi, Fibonacci or even an exploration algorithm for a minesweeper). But what about mutually recursive calls? Start with maths here as well. f(x) = g(x) + h(x) where g(x) = f(x) + l(x) and h and l just do stuff.

Starting with just mathematical series makes it easier to write and implement as the contract is clearly defined by the expressions. For instance, the Hofstadter Female and Male Sequences:

However in terms of code, it is to be noted that the implementation of a mutually recursive solution often leads to code duplication and should rather be streamlined into a single recursive form (See Peter Norvig's Solving Every Sudoku Puzzle.

Answer 2

The calling of a function from within that same function.

Answer 3

Recursion is a function that calls itself.

How to use it, when to use it and how to avoid bad design are important to know, which requires you to try it out for yourself, and understand what happens.

The most important thing you need to know is to be very careful to not get a loop that never ends. The answer from pramodc84 to your question has this fault: It never ends...
A recursive function must always check for a condition to determine if it should call itself again or not.

The most classic example to use recursion, is to work with a tree with no static limits in depth. This is a task that you must use recursion.

Answer 4

Okay i am going to try to keep this simple and concise.

Recursive function are functions that call themselves. Recursive function consist of three things:

1. Logic
2. A call to itself
3. When to terminate.

Best ways to write recursive methods, is to think of the method that you trying to write as a simple example only handling one loop of the process you want to iterate over, then add the call to the method itself, and add when you want to terminate. Best way to learn is to practice like all things.

Since this is programmers website I will refrain from writing code but here is a good link

if you got that joke you got what recursion means.

Answer 5

Recursive programming is the process of progressively reducing a problem in to easier to solve versions of itself.

Every recursive function tends to:

1. take a list to process, or some other structure, or problem domain
2. deal with the current point/step
3. call itself on the remainder(s)/subdomain(s)
4. combine or use the results of the subdomain work

When step 2 is before 3, and when step 4 is trivial (a concatenation, sum, or nothing) this enables tail recursion. Step 2 often must come after step 3, as the results from the subdomain(s) of the problem may be needed in order to complete the current step.

Take the traversal of a straight forward binary tree. The traversal can be made in pre-order, in-order, or post-order, depending on what is required.

   B
A     C

Pre-order: B A C

traverse(tree):
    visit the node
    traverse(left)
    traverse(right)

In-order: A B C

traverse(tree):
    traverse(left)
    visit the node
    traverse(right)

Post-order: A C B

traverse(tree):
    traverse(left)
    traverse(right)
    visit the node

Very many recursive problems are specific cases of a map operation, or a fold - understanding just these two operations can lead to significant understanding of good use-cases for recursion.

Answer 6

The OP said that recursion doesn't exist in the real world, but I beg to differ.

Let's take the real world 'operation' of cutting up a pizza. You've taken the pizza out of the oven and in order to serve it up you have to cut it in half, then cut those halves in half, then again cut those resultant halves in half.

The operation of cutting the pizza you performing again and again until you've got the result you want (the number of slices). And for arguments sake let's say that an uncut pizza is a slice itself.

Here's an example in Ruby:

def cut_pizza(existing_slices, desired_slices)
  if existing_slices != desired_slices
    # we don't have enough slices yet to feed everyone, so
    # we're cutting the pizza slices, thus doubling their number
    new_slices = existing_slices * 2 
    # and this here is the recursive call
    cut_pizza(new_slices, desired_slices)
  else
    # we have the desired number of slices, so we return
    # here instead of continuing to recurse
    return existing_slices
  end
end

pizza = 1 # a whole pizza, 'one slice'
cut_pizza(pizza, 8) # => we'll get 8

So the real world operation is cutting a pizza, and the recursion is doing the same thing over and over until you have what you want.

Operations you'll find that crop up that you can implement with recursive functions are:

• Calculating compound interest over a number of months.
• Looking for a file on a file system (because file systems are trees because of directories).
• Anything that involves working with trees in general, I guess.

I recommend writing a program to look for a file based on it's file name, and try to write a function that calls itself until it's found, the signature would look like this:

find_file_by_name(file_name_we_are_looking_for, path_to_look_in)

So you could call it like this:

find_file_by_name('httpd.conf', '/etc') # damn it i can never find apache's conf

It's simply programming mechanics in my opinion, a way of cleverly removing duplication. You can rewrite this by using variables, but this is a 'nicer' solution. There is nothing mysterious or difficult about it. You'll write a couple of recursive functions, it'll click and huzzah another mechanical trick in your programming tool box.

Extra Credit The cut_pizza example above will give you a stack level too deep error if you ask it for a number of slices that isn't a power of 2 (i.e 2 or 4 or 8 or 16). Can you modify it so that if someone asks for 10 slices it wont run for ever?

Answer 7

Recursion is a tool a programmer can use to invoke a function call on itself. Fibonacci sequence is the textbook example of how recursion is used.

Most recursive code if not all can be expressed as iterative function, but its usually messy. Good examples of other recursive programs are Data Structures such as trees, binary search tree and even quicksort.

Recursion is used to make code less sloppy, keep in mind it is usually slower and requires more memory.

Answer 8

I like to use this one:

How do you walk to the store?

If you're at the entrance to the store, simply go through it. Otherwise, take one step, then walk the rest of the way to the store.

It's critical to include three aspects:

• A trivial base case
• Solving a small piece of the problem
• Solving the rest of the problem recursively

We actually use recursion a lot in daily life; we just don't think of it that way.

Answer 9

The best example that I would point you to is C Programming Language by K & R. In that book (and I am quoting from memory), the entry in index page for recursion (alone) lists the actual page where they talk about recursion and the index page as well.

Answer 10

Recursion n. - A pattern of algorithm design where an operation is defined in terms of itself.

The classic example is finding the factorial of a number, n!. 0!=1, and for any other natural number N, the factorial of N is the product of all natural numbers less than or equal to N. So, 6! = 6*5*4*3*2*1 = 720. This basic definition would allow you to create a simple iterative solution:

int Fact(int degree)
{
    int result = 1;
    for(int i=degree; i>1; i--)
       result *= i;

    return result;
}

However, examine the operation again. 6! = 6*5*4*3*2*1. By the same definition, 5! = 5*4*3*2*1, meaning that we can say 6! = 6*(5!). In turn, 5! = 5*(4!) and so on. By doing this, we reduce the problem to an operation performed on the result of all previous operations. This eventually reduces to a point, called a base case, where the result is known by definition. In our case, 0!=1 (we could in most cases also say that 1!=1). In computing, we are often allowed to define algorithms in a very similar way, by having the method call itself and pass a smaller input, thus reducing the problem through many recursions to a base case:

int Fact(int degree)
{
    if(degree==0) return 1; //the base case; 0! = 1 by definition
    else return degree * Fact(degree -1); //the recursive case; N! = N*(N-1)!
}

This can, in many languages, be further simplified using the ternary operator (sometimes seen as an Iif function in languages that don't provide the operator as such):

int Fact(int degree)
{
    //reads equivalently to the above, but is concise and often optimizable
    return degree==0 ? 1: degree * Fact(degree -1);
}

Advantages:

• Natural expression - for many types of algorithms, this is a very natural way to express the function.
• Reduced LOC - It's often much more concise to define a function recursively.
• Speed - In certain cases, depending on language and computer architecture, recursion of an algorithm is faster than the equivalent iterative solution, usually because making a function call is a faster operation at the hardware level than the operations and memory access required to loop iteratively.
• Divisibility - Many recursive algorithms are of the "divide and conquer" mentality; the result of the operation is a function of the result of the same operation performed on each of two halves of the input. This allows you to split the work in two at each level, and if available you can give the other half to another "execution unit" to process. This is typically harder or impossible with an iterative algorithm.

Disadvantages:

• Requires understanding - You simply must "grasp" the concept of recursion in order to understand what's going on, and therefore write and maintain effective recursive algorithms. Otherwise it just looks like black magic.
• Context-dependent - Whether recursion is a good idea or not depends on how elegantly the algorithm can be defined in terms of itself. While it is possible to build, for example, a recursive SelectionSort, the iterative algorithm is typically the more understandable.
• Trades RAM access for call stack - Typically, function calls are cheaper than cache access, which can make recursion faster than iteration. But, there's usually a limit to the depth of the call stack that can cause recursion to error where an iterative algorithm will work.
• Infinite recursion - You have to know when to stop. Infinite iteration is also possible but the looping constructs involved are usually easier to understand and thus to debug.

Answer 11

The example I use is a problem I faced in real life. You have a container (such as a large backpack you intend to take on a trip) and you want to know the total weight. You have in the container two or three loose items, and some other containers (say, stuff sacks.) The weight of the total container is obviously the weight of the empty container plus the weight of everything in it. For the loose items, you can just weigh them, and for the stuff sacks you could just weigh them or you could say "well the weight of each stuffsack is the weight of the empty container plus the weight of everything in it". And then you keep going into containers into containers and so on until you get to a point where there are just loose items in a container. That's recursion.

You may think that never happens in real life, but imagine trying to count, or add up the salaries of, people in a particular company or division, which has a mixture of people who just work for the company, people in divisions, then in the divisions there are departments and so on. Or sales in a country that has regions, some of which have subregions, etc etc. These sorts of problems happen all the time in business.

Answer 12

Recursion can be used to solve a lot of counting problems. For example, say you have a group of n people at a party (n > 1), and everyone shakes everyone else's hand exactly once. How many handshakes take place? You may know that the solution is C(n,2) = n(n-1)/2, but you can solve recursively as follows:

Suppose there are just two people. Then (by inspection) the answer is obviously 1.

Suppose you have three people. Single out one person, and note that he/she shakes hands with two other people. After that you have to count just the handshakes between the other two people. We already did that just now, and it is 1. So the answer is 2 + 1 = 3.

Suppose you have n people. Following the same logic as before, it is (n-1) + (number of handshakes between n-1 people). Expanding, we get (n-1) + (n-2) + ... + 1.

Expressed as a recursive function,

f(2) = 1
f(n) = n-1 + f(n-1), n > 2

Answer 13

In life (as opposed to in a computer programme) recursion rarely happens under our direct control, because it can be confusing to make happen. Also, perception tends to be about the side effects, rather than being functionally pure, so if recursion is happening you might not notice it.

Recursion does happen out here in the world though. A lot.

A good example is (a simplified version of) the water cycle:

• The sun heats the lake
• The water goes up into sky and forms clouds
• The clouds drift over to a mountain
• At the mountain the air becomes too cold for their moisture to be retained
• Rain falls
• A river forms
• The water in the river runs into the lake

This is a cycle that causes its self to happen again. It is recursive.

Another place you can get recursion is in English (and human language in general). You might not recognise it at first, but the way we can generate a sentence is recursive, because the rules allow us to embed one instance of a symbol in side another instance of the same symbol.

From Steven Pinker's The Language Instinct:

if either the girl eats ice cream or the girl eats candy then the boy eats hot dogs

That is a whole sentence that contains other whole sentences:

the girl eats ice cream

the girl eats candy

the boy eats hot dogs

The act of understanding the full sentence involves understanding smaller sentences, which use the same set of mental trickery to be understood as the full sentence.

To understand recursion from a programming perspective it's easiest to look at a problem that can be solved with recursion, and understand why it should be and what that means you need to do.

For the example I will use the greatest common divisor function, or gcd for short.

You have your two numbers a and b. To find their gcd (assuming neither is 0) you need to check if a is evenly divisible into b. If it is then b is the gcd, otherwise you need to check for the gcd of b and the remainder of a/b.

You should already be able to see that this is a recursive function, as you have the gcd function calling the gcd function. Just to hammer it home, here it is in c# (again, assuming 0 never gets passed in as a parameter):

int gcd(int a, int b)
{   
    if (a % b == 0) //this is a stopping condition
    {
        return b;
    }

    return (gcd(b, a % b)); //the call to gcd here makes this function recursive
}

In a programme, it is important to have a stopping condition, otherwise you function will recur forever, which will eventually cause a stack overflow!

The reason to use recursion here, rather than a while loop or some other iterative construct, is that as you read the code it tells you what it is doing and what will happen next, so it is easier to figure out if it is working correctly.

Answer 14

Here is a real world example for recursion.

Let them imagine that they have a comic collection and you're going to mix it all up into a big pile. Careful -- if they really have a collection, they may instantly kill you when you just mention the idea to do so.

Now let them sort this big unsorted pile of comics with the help of this manual:

Manual: How to sort a pile of comics

Check the pile if it is already sorted. If it is, then done.

As long as there are comics in the pile, put each one on another pile, 
ordered from left to right in ascending order:

    If your current pile contains different comics, pile them by comic.
    If not and your current pile contains different years, pile them by year.
    If not and your current pile contains different tenth digits, pile them 
    by this digit: Issue 1 to 9, 10 to 19, and so on.
    If not then "pile" them by issue number.

Refer to the "Manual: How to sort a pile of comics" to separately sort each
of the new piles.

Collect the piles back to a big pile from left to right.

Done.

The nice thing here is: When they are down to single issues, they have the full "stack frame" with the local piles visible before them on the ground. Give them multiple printouts of the manual and put one aside each pile level with a mark where you currently are on this level (ie. the state of the local variables), so you can continue there on each Done.

That's what recursion basically is about: Performing the very same process, just on a finer detail level the more you go into it.

Answer 15

Josh K already mentioned the Matroshka dolls. Assume that you want to learn something that only the shortest doll knows. The problem is that you can't really talk to her directly, because she originally lives inside the taller doll which on the first picture is placed on her left. This structure goes like that (a doll lives inside the taller doll) until ending up only with the tallest one.

So the only thing that you can do is to ask your question to the tallest doll. The tallest doll (who doesn't know the answer) will need to pass your question to the shorter doll (which on the first picture is on her right). Since she also doesn't have the answer she needs to ask the next shorter doll. This will go like that until the message reaches the shortest doll. The shortest doll (who is the only one who knows the secret answer) will pass the answer to the next taller doll (found on her left), which will pass it to the next taller doll... and this will continue until the answer reaches its final destination, which is the tallest doll and finally... you :)

This is what recursion really does. A function/method calls itself until getting the expected answer. That's why when you write recursive code it's very important to decide about when recursion should terminate.

Not the best explanation but it hopefully helps.

Answer 16

• Terminate if exit condition reached
• do something to alter the state of things
• do the work all over starting with the present state of things

Recursion is a very concise way to express something that has to be repeated until something is reached.

Answer 17

Not plain english, not really real life examples, but two ways of learning recursion by playing:

• Tower of Hanoi
• Baguenaudier

Answer 18

A nice explanaition of recursion is literally 'an action that reoccurs from within itself".

Consider a painter painting a wall, it's recursive because the action is "paint a strip from ceiling to floor than scoot over a little to the right and (paint a strip from ceiling to floor than scoot over a little to the right and (paint a strip from ceiling to floor than scoot over a little to the right and ( etc )))".

His paint() function calls itself over and over again to make up his bigger paint_wall() function.

Hopefully this poor painter has some kind of stop condition :)