The Basics of Recursion vs Iteration

Today’s topic was chosen by Prad N, who attends UT Austin. The original topic as proposed was “recursion vs iteration with stacks”; however, that is a fairly narrow—and somewhat technical—topic, so this blog post will discuss recursion and plain old iteration.

First off, recursion and iteration are terms used in computer science. Iteration, essentially, is a process by which you count something or carry out a number of steps, in order. For instance, if you want to write a program that subtracts one dollar from every bank account in the world and adds it to your own, you would be illicitly iterating through a bunch of bank accounts.

Recursion is a process by which something refers to itself, such as this sentence.

That would be called a recursive sentence, because of the phrase “this sentence.” In logic, recursion can lead to paradoxes, such as “This sentence is false.” Anyways…

In computer programming, recursion is when a function calls itself. Here’s an example. Say you write a program that has three steps, A, B, and then C. If the program just executes them in order, it would be iterative. But suppose in step A, one of the things to do is to run step A. That is recursion.

But wait, you say! If one of the things to do in step A is to do step A, wouldn’t that require another run of step A, and wouldn’t that one as well, etc.? If done poorly, recursion can do this. The program would never end.

For a real example, consider the mathematical factorial function,

n! = n(n-1)(n-2)\cdots(3)(2)(1)

There is a recursive way to define the function, namely that

n! = n\cdot(n-1)!

There is something missing here, however, and it is that it has no endpoint. If we wanted to figure out 3! using this method, we find that it is equal to 3*2! = 3*2*1! = 3*2*1*0! = …. Of course, we want to make it clear that 1! = 1. So the recursive definition must have both a formula AND a way to end:

n! = n\cdot(n-1)!, 1! = 1

In Java, we would have something like this:

int factorial(int n) {
  if (n==1) return 1;
  return n * factorial(n-1);
}

Here’s what it’s doing in English. Suppose you input the number 4.  It will run the line starting with “if”, and because 4 does not equal 1, it will move on to the next line. This tells the function to return n * factorial(n-1), which is, in this case, 4 * factorial(3). But factorial(3) is just 3 * factorial(2), Using substitution, we have factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2). Continuing on, we have factorial(2) = 2 * factorial(1). Here is the ending step, because factorial(1) will trigger the “if” condition and cause it to run “return 1” and skip the recursive line. So 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1) = 4 * 3 * 2 * 1. At this point, the computer will just calculate the product and spit out 24.

Of course, one can do it iteratively as well:

int factorial(int n) {
  int i = 1;
  int product = 1;
  while(i < n) {
    i = i + 1;
    product = product * i;
  }
  return product;
}

I won’t explain it in full this time. The idea is that it multiplies all the integers from 1 up to the number you input. The two algorithms do essentially the same thing, but one does it by calling itself and other other by running a loop. Recursion is usually more fun.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s