Introduction to Recursion

Tue, Jan 24, 2023 3-minute read

Recursion is a mind-bending topic.

Once you make a few methods, you may start to wonder, ‘can I call this method from inside the method, Inception-style?’.

Well, yes, you can. It’s a bit mind-boggling but this is the fun part of programming, where you can feel your brain being stretched.

Recursion can make some problems far easier to solve and even in cases where the iterative method (loops), just won’t work. The problem is that it is very hard to visualise and understand how this works.

And how do we stop the method from calling itself from within itself forever, dooming us to an infinite loop and sucking our entire program into a black hole of its own making, CERN-style? (hint: always have a base case)

Here’s a code example with just three lines in the onion() method to try to explain recursion as simply as possible. Let’s use onions (thanks, Pondy). 🧅🧅🧅

class OnionMaker {
    public void onion (int layers){
         // 1, print the left side of layer
        System.out.print("(");

       // 2. check if layer is more than one, if so call onion() again
       // this is the recusive part, and also the base case
        if (layers > 1) { this.onion(layers-1); }

         // 3. print the right side of layer
        System.out.print(")");
    }

    // Just need this to call the onion maker
    public static void main(String[] args) {
        OnionMaker om = new OnionMaker();
        om.onion(3); // ((()))

    }
}

Ok, here’s a way to think about this in order:

(1) ok, I’m going in with 3 layers onion(3) 🧅🧅🧅
(2) print (
(3) is layers (3) more than 1?
- (4) yes ✅
  - (5) go though onion() again but with 1 fewer layer onion(2) 🧅🧅
    - (6) print (
      - (7) is layers (2) more than 1?
        
        (8) yes ✅
        
        (9) go though onion() again but with one fewer layer onion(1) 🧅
        
        (10) print (
        
        (11) is layers (2) more than 1?
        
        (12) no. ❌ (ok, continue on this method)
        
        (13) print ) - finishing onion(1) 🧅
        
        (14) finish
(15) print ) - finishing onion(2) 🧅🧅
(16) print ) - finishing onion(3) 🧅🧅🧅

Output: ((()))

Steps in Recursion vs Iteration

Iteration:
- break problem into sequence of the typical case
- identify the typical case (body)
- identify the increment to step to the next case
- identify the keep-going or stopping condition
- identify the initialisation
Recursion: (simple)
- break problem into first and rest
- identify the first case
- identify the recursive call for the rest
  - work out the arguments for the rest
- identify when you should do the recursive call.
  - make sure there is a stopping case (base case)
- may need a wrapper method to initialise

Git Forked

Introduction to Recursion

Steps in Recursion vs Iteration