Difference Between Recursion and Iteration

russian-dolls

If you are learning algorithms or data structures, you might have come across the terms recursion and iteration. Knowing the difference between the two can be confusing, so I will explain both terms using a real-world example.

Eating My Morning Bowl of Oatmeal

eating-oatmeal

Everyday before I go to work, I take a shower, get dressed, and then head over to the kitchen to fix myself a big bowl of oatmeal. Breakfast is my favorite meal of the day and the most important. Many days I feel like skipping breakfast so that I can go on with my day. However, on those rare occasions when I decide to skip breakfast, I have usually regretted it. I spend the morning hungry and cannot fully concentrate on the tasks at hand.


The problem of eating my morning bowl of oatmeal can be implemented both iteratively and recursively. Iteration is the act of repeating a process. So, in the case of oatmeal, an iterative way to solve the problem of eating my bowl of oatmeal would be to do the following:

  1. Take one bite of the oatmeal
  2. Repeat Step 1 until the bowl is empty.

Recursion, on the other hand, is when a method calls itself. It involves breaking a problem into smaller versions of the same problem until you reach a trivial stopping case.

Let’s consider the problem of eating a bowl of oatmeal. I can solve the problem of eating the entire bowl of oatmeal recursively by breaking it into two subproblems as follows:

  • Take one bite of oatmeal
  • Eat the rest of the bowl of oatmeal

Each step of this recursive procedure gets smaller and smaller until all I am left with is one more spoonful of oatmeal. Once I finish that last spoonful, I am done, and I can go on about my day.

Here is how I would implement the iterative and recursive procedures for eating a bowl of oatmeal in Java pseudocode:

Iterative Implementation

public static main void main(String[] args) {

    while (!bowl.empty()) {
        bowl.takeOneBite(); 
        // Keep taking bites over and over 
        // again until the bowl of oatmeal 
        // is empty
    }
}

Recursive Implementation

public static void eatOatmeal(Bowl bowl) {

    if (bowl.empty()) {  
    // This is our stopping case. 
    // We stop taking bites once 
    // the bowl is empty

        return;  
    }
    else {
        bowl.takeOneBite(); 
        eatOatmeal(bowl); // Recursive call
    }
}