Problem Statement

Given a string containing numbers from 2-9 enumerate all possible combinations that the number could represent. Each number is mapped to 3 or 4 digit code as shown in the image below.

For example

Input:"23"
Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

If we assume that every number has 3 character long code then the number of possible combinations for string of length n will be 3^n. Example above a string of length 2 you will get 3^2 possible combinations. This problem is really extension of String permutation about which I wrote in previous blog. Below is source code for solving the problem using recursion.

public class PhoneNumberDigits {

  public static Map<Character, String> lookup = new HashMap<>();

  static {
    lookup.put('2', "abc");
    lookup.put('3', "def");
    lookup.put('4', "ghi");
    lookup.put('5', "jkl");
    lookup.put('6', "mno");
    lookup.put('7', "pqrs");
    lookup.put('8', "tuv");
    lookup.put('9', "wxyz");
  }

  public static List<String> enumerate(String digits) {
    List<String> results = new ArrayList<>();
    enumerate("", digits, results);
    return results;
  }

  private static void enumerate(String prefix, String digits, List<String> results) {
    if (!digits.isEmpty()) {
      char currentChar = digits.charAt(0);
      String charCode = lookup.get(currentChar);
      for (int i = 0; i < charCode.length(); i++) {
        enumerate(prefix + charCode.charAt(i), digits.substring(1), results);
      }
    } else {
      results.add(prefix);
      return;
    }
  }
}

Problem Statement

The problem we are going to formalute a solution is as follows
Given a string of of size ‘n’ find all permutations of the string.
So if given string is “abc” the answer will be {‘abc’,’acb’,’bac’,’bca’,’cab’,’cba’}. So for a string of size n the number of permutations we will have is n!. When string is size=3 the permutations function will return an array of 3!(factorial) strings which is 6 strings.This problem has a very elegant solution if expressed via recursion. Let us try to build our intuition for this problem first before we write any code. We will look at string “abc” and try to break down the problem in recursive template.
permutation(“abc”) can be broken down into one set of subproblem such as a + permutation(“bc”). Suppose I told you that the permutation(“bc”) will be provided to you, then your problem will be simple as prepending ‘a’ to the strings in result set. It will look something like this
permutation(“bc”) –> [“bc”, “cb”] and now we prepend ‘a’ to these individual strings to get the following set [“abc”, “acb”]. This provides us the partial subset of our answer. Similarly we will have to do this for every character in the string. See below

b + permutation("ac")
b + ["ac", "ca"]
["bac", "bca"]

c + permutation("ab")
c + ["ab", "ba"]
["cab", "cba"]

There is pattern that we can present with an equation –
permutation(string) –> for every character in string
do : prepend current char + permutation(string without current char)

There is one thing missing in our recursive strategy and that is the base case. The base case in our problem will be when the string is of size 0 we return. The code of this problem becomes very simple

public class PermuteString {

  public static void permute(String orginal) {
    permute("", orginal);
  }
  
  public static void permute(String current, String remaining) {
    if(remaining.isEmpty()) {
      System.out.println(current);
      return;
    }
    
    //Go through each character in string and perform this  
    // current char + permutation(remaining string)  
    // remaining string -- the original string minus the currently selected  
    //character
    for(int i=0; i < remaining.length(); i++) {
      char c = remaining.charAt(i);
        
      permute(c+current, remaining.substring(0,i) + remaining.substring(i+1));
    }
  }

  public static void main(String[] args) {
    permute("abc");
  }
}

Introduction

In this blog post I will try to give an intuition behind recursion and also discuss things that helped me understand the topic very well. Grasping recursion truly opens up solutions to many programming problems which otherwise would have to be coded with quite a bit of complexity.

What is recursion?

Many programming text books define recursion as a function that calls itself. Although the definition is sound, I feel it is incomplete and does not give you the intuition behind why and where recursion comes into play. I like to think of recursion as a technique in which you break down a problem into smaller subproblems and then combine the solution of a smaller problem to deduce the final solution you need. There is a lot of intuition behind recursion if you compare it to Principle of Mathematical Induction (PMI). PMI is a technique used to prove theorems or a formula. There are typically 3 steps involved in PMI. Lets try to prove a sum of n integers Sum(n) = n(n+1)/2

• Base case
  Prove the formula or theorem is true for small n. In this case n=1 Therefore sum(1) = 1(1+1)/2 = 2/2 = 1
• Induction hypothesis
  Assume sum(n) = n(n+1)/2 is true for some n
• Prove that the theorem is true for n+1 using steps 1 and 2
  Sum(n+1) = (n+1) ((n+1)+1)/2
  1+2+3+…+n+1 = (n+1)((n+1)+1)/2
  LHS can be written as
  n(n+1)/2 + n+1 = (n+1)(n+2)/2
  factoring out n+1 we get
  (n+1)(n+2)/2 which is equal to RHS
  Now that we have a refresher on PMI lets look at how we can apply this in our recursive problem solving thinking.

Recursive thinking

In this section we build up some techniques that, once mastered, can be utilized as templates for solving many recursive problems. One common mistake I see people make is to try to visualize and think through how recursive calls will work. This is ok when a problem domain is small but for complex problems this can get tedious and unreasonable. In some ways we have to assume that the solutions for smaller subproblems will work and are correct and all we have to do is apply or combine the smaller solutions to build the complete solution. This is very much like Induction hypothesis, where we assume that proof is true for some n and have to prove it is true for n+1. This is what many people call Recursive leap of faith. Lets look at what I mean by Recursive leap of faith with an example. Suppose you are in a group of 500 people standing right next to each other. The goal of this group is to figure out a total salary of the entire group. Imagine that you are the last person in the group. If I told you that a person beside you will accurately tell you the sum of salaries for all other 499 people then your problem becomes relatively simple. All you will have to do is add your own salary + sumOfSalaries(499 other people) and you are done. Here you believed that the number returned by the person on your right is correct and you did not look into how it was calculated. Your task was pretty simple, add your own salary to this number and pass it to the person next to you. Here you took Recursive leap of faith and believed in the process to work itself out. Thus we broke down the problem into smaller subproblems and believed in the recursive process to work itself out. Of course there are few more things we will need to address such as base case, etc but at this point you understand what I mean by breaking down the problem and trusting that recursion will work itself out. The person at the 499 position did exactly the same; he added his own salary to sumOfSalaries(498 other people) and returned the value to you. Let’s see how the pseudo code would look like

1
2
3
4
5
6
7
8
9
10
11
   int sumOfSalaries(int currentIndex, int n, int salaries[]) {  
      if(currentIndex == 0){  
        return salaries[currentIndex];  
      }  
    return salaries[currentIndex] + sumOfSalaries(currentIndex--, n, salaries);  
 }
 
 int aggregateSalary = sumOfSalaries(500-1, 500, salaries);
 /* Where salaries is an array that contains salary of all  
   500 ppl.n is total number of people  
   */

If you look at the code above you will see at line 5 you add your own salary to the aggregate salaries of all prior. The base case is when you are the first person in the line. In that case we treat the problem as just returning the current salary.
Lets look at another tricky problem that has an elegant recursive solution. Invert a binary tree:
Given a binary tree, our goal is to invert it. See the image below

Lets put on our recursive thinking hat and break down the problem. First at any given node we expect the right and left subtree below the node have already been inverted. Once that has happened our task is simply to replace the current nodes left subtree with the current nodes right subtree and vice-versa. So we take a Recursive leap of faith in assuming that our left and right child subtrees have already been reverted and now our current task only has to swap the left and right child. Lets see how we express this in pseudo code.

   invert(node n) {
       if n is null return
       invert(left child of n)
       invert(right child of n)
       swap left and right child of n.
   }

It turns out using recursion the solution to this problem turns out to be very compact code and very natural to express in terms of recursive strategy. See code below

   public class InvertBinaryTree {
  
  public static class Node {
    public Node left, right;
    public int val;
    public Node(int v) {
      this.val = v;
    }
  }
  
  public static void invert(Node n) {
    if(n == null) {
      return;
    }
    //Invert my left subtree first
    invert(n.left);
    // Then invert my right subtree
    invert(n.right);
    //If i come here it means my left and right child subtrees 
    //are already inverted and now
    // my task is to simply swap my children 
    Node temp = n.left;
    n.left = n.right;
    n.right = temp;
  }

  public static void main(String[] args) {
    Node n20  = new Node(20);
    Node n35 = new Node(35);
    Node n15 = new Node(15);
    Node n10 = new Node(10);
    Node n18 = new Node(18);
    Node n40 = new Node(40);
    
    n20.left = n15;
    n20.right = n35;
    n15.left = n10;
    n15.right = n18;
    n35.right = n40;
    invert(n20);
  }
}

Good resources

• https://www.codingninjas.in
• https://www.amazon.com/Introduction-Recursive-Programming-Manuel-Rubio-Sanchez/dp/1498735282

This is my attempt to write about my experience with different technologies, algorithms, machine learning and at times about life and people in general. As a starter post I promise to keep it short.I have been very fortunate in my life to have opportunities that were presented to me. Ofcourse, I realized this little late but you live and learn. I think that is more important. Life should be about evolution and trying to be the better version of yourself everyday. I am forever grateful to many people who have helped me in life so far. They know who they are. As promised this post will be short and sweet.