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.

Going Viral: Planning vs. the Internet

Almost a month ago, on November 18, I was stumbling on the Internet, taking a break from novel-writing for NaNoWriMo. I was in the Olin Library, at Cornell University. Suddenly I had the idea to make a diagram of how I waste a lot of time on the Internet. That became the now viral “Planning vs. the Internet” image (here’s the original post):

The only software I used were Microsoft Publisher (I just created a very long, blank sheet), Paint, and GIMP. The most painful part was actually getting all the icons and aligning things together.

I was first notified of its viral factor when the viewcount on my blog spiked. It wasn’t very much. The daily views went from an average of 150 suddenly to 600. I have experienced a really big spike (80,000 in one day) in the past, but I knew there was something weird here, because I tracked a relatively large number of hits on the home page, not on any post in particular. I wasn’t really sure what to make of this.

Then two real-life friends from two different places messaged me on Facebook, saying that they had stumbled upon this image. I immediately did a google search for *planning vs the internet* but found only a few websites that had uploaded the image, and so were gaining viewcount for themselves. This made sense. The only identification on this image is the blurb I put on the bottom right corner, which  goes to my homepage, so it would make sense that I received a homepage spike. But of all the websites I found put together, plus this site itself, I counted at most 2000 views. It was too coincidental that two of these 2000 would be people I knew in real life. There must be views coming from something else, something that wasn’t stat tracked. This was all a few days prior to this post.

Then just an hour ago, I found it. THIS.

That was it. A huge spike from StumbleUpon. 269K views at the time of this post. But the url stumbled is the image file itself, not the post in which I put up the image. So WordPress is actually not keeping track of any of these 269K hits. That’s why, on the right-hand bar, it says 230,367 views (at the time of the current post), which is lower than the amount on the image alone. Too bad it doesn’t count. Had it counted, it would have over doubled the total number of hits on this blog.