Category Archives: Recursion

Number of ways to make coin change

Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination.

For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities are {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}. So there are 4 possibilities in total.

Let us try to solve this problem using recursion. Let N be the amount for which we have to make change, and D is the set of denominations. Assume we have a method Count which takes in the parameter amount N, and the index of current denomination, we can have pseudo code like this

Count(N, index)

  • Base case#1: If N < 0 or index < 0 return 0. There is no way to make change for negative numbers or if there are no denominations
  • Base case#2: If N == 0, return 1. There is only one possibility to make change for 0 amount, selecting none.
  • Otherwise return Count(N, index-1) + Count( N-D[index], index ). Either ignore the current denomination (First term), or take the current denomination(second term) and recurse accordingly.

Since this recursive method solves the same problem multiple times, we can think of a dynamic programming solution for this problem. In dynamic programming, we solve the smaller sub problems first and use their results in solving bigger sub problems. We store the results in a table. Lets create a table[N+1][M] where N is the amount, and M is the denomination count.

  • table[0][j] = 1, Only one way to make 0.
  • table[i][0] = 1 if N is divisible by D[0], otherwise 0
  • table[i][j] = table[i][j-1] if D[j] > i
    = table[i][j-1] + table[i- D[j]][j]

Here is the Java code which implements the above approach.

Generating all possible parenthesis expressions

Given a number N, how do we generate all possible valid expressions with N pairs of brackets?

For example for N = 2, there are 2 such expressions
()()
(())
For N = 3, there are 5 expressions
((()))
(()())
(())()
()(())
()()()

We have a simple solution to this problem by using recursion. We design this method as follows.

It takes two parameters left count, right count, buffer and an index. At each index we can either fill a left bracket or a right bracket.

As long as we have left brackets, we try to fill them and recursively call the method with one less left brace.


Then we check if we have more right braces than left braces, then fill it up with right brace. Recursively call the method with one less right brace.

When we don’t have any left or right braces remaining, we can print the contents of the buffer.

Here is the Java implementation.

Checking if a binary tree is balanced

Given a binary tree, how do we check if it is balanced or not?
We say that a binary tree is balanced if height difference of left  and the right sub-trees is at most 1 at  any node.

Consider the following examples

  1          1               1             1
 /                       /              
2   3          2           2                 2
                                           /
                                          3
Balanced    Balanced     Balanced       Unbalanced

Solution:

We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it’s left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).

Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it. 

We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.

Here is the C++ implementation of this algorithm. It runs in O(n) time.

Longest path in a binary tree

Given a binary tree, how do we find the longest distance between any two nodes in it? Some times this is referred to as the diameter of the tree.
For example consider the below binary tree

The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7. In this example the longest path passes through the root node. Sometimes it may not pass through the root. Checkout the next example.

The longest path 27-28-24-36-42-59-55 does not include the root node.

Here is how we can find the longest path recursively. We know that the height of the binary tree is the longest path from the root node to any leaf node.(Read this post to know more). Diameter is the maximum of the following.

Height(left subtree) + Height(right subtree) + 1
Diameter(left subtree)
Diameter(right subtree)

Here is the C++ implementation of the above. This program calculates the number of nodes on the longest path. The time complexity for this solution is O(n2). For optimal implementation, you can checkout this post.

Printing all K combinations from N numbers

Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,…N}.

For example consider N = 4, K = 3, the possible combinations are
[
 [1, 2, 3]
 [1, 2, 4]
 [2, 3, 4]
 [1, 3, 4]
]

Let us look how to solve this combination problem. This problem can be recursively defined as follows. To generate K-combinations from N elements, we have two possibilities.
  1. Generate K-Combinations from (N-1) elements.
  2. Generate (K-1)-Combinations from (N-1) elements and append N to all of them.
Let us simulate this with an example. Assume N = 3, K = 2

Generate 2-Combinations from 2 elements i.e N = 2, K = 2
This will be just one combination i.e [1, 2]

Generate 1-Combinations from 2 elements i.e N = 2, K = 1
[1], [2]
Append 3 to each of them
[1, 3], [2,3]

So there are totally 3 combinations [ [1, 2], [1, 3], [2, 3] ].

Here is the recursive implementation in C++.

Finding the magic index of the array

Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.

For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
If there no such element in the array we can return -1.

Very obvious approach is to do a linear search to find such an element. This will take O(n) in the worst case.

Since the array is sorted, we can modify the binary search to solve this problem more efficiently.

Using binary search we first visit the middle element of the array. 
If array[mid] = mid, simply return mid.
If mid > array[mid], there is no way to find magic index on the left half. Think of an example
[-10, -3, 0, 2, 4, 8]. Here middle index = 3, array[3] = 2.   If we go back from index 3, we can only find elements less than 2 because the array is sorted and it has distinct elements. Hence we can safely skip the left half and proceed to search the right half effectively reducing your search space by half.

In the same way, if mid < array[mid], we can ignore the right half and search only left half of the array.

C++ implementation of the above algorithm is given below.

Traversals of a binary tree

Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure.

There are three main traversals of the binary tree. Namely

  • In-order traversal
  • Post-order traversal
  • Pre-order traversal
In addition to these, there are inverses of the above algorithms, and there is a level order traversal.

In this post we will see the three main traversal algorithms mentioned above. All of these are defined as recursive algorithms.
In In-order traversal, we first visit the left sub-tree, then root, and then the right sub-tree.
In Post-order traversal, we first visit the left sub-tree, then the right sub-tree, and then the root.
In Pre-order traversal, We first visit the root, then visit the left sub-tree and then visit the right sub-tree.

For example consider the simple  3 node binary tree

In-order traversal: B  A  C
Post-order traversal: B  C  A
Pre-order traversal: A  B  C

To consider a bigger example, take the following binary search tree and it’s traversal sequences for the three algorithms.

In-order: 1  2  3  4  5  6  7  8

Post-order: 1  2  4  3  7  6  8  5
Pre-order: 5  3  2  1  4  8  6  7 
The in-order traversal of the binary search tree always produces the sorted order of it’s elements.

Here is the C++ code for all the traversals.

Finding the height of the binary tree

Given a binary tree how to find the height of the tree. 
It is defined as the number of nodes in the longest path from root to any leaf.

 We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the below tree has a height of 4.

We can calculate the height of the tree using recursive method very easily. It is based on the observation that height of a binary tree is 
1 + Max( height(left-sub-tree), height(right-sub-tree) )
Here is the C++ code which implements this simple algorithm.

Print a string in reverse using recursion

The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the function returns and we print the character at the current pointer.

Since the function calling mechanism uses a stack to keep track the calling sequence. While unwinding the stack, we are able to print the characters in reverse.

For example printReverse(“hello”) function calling sequence looks like the following.
printReverse(“hello”)
  printReverse(“ello”)
    printReverse(“llo”)
      printReverse(“lo”)
        printReverse(“o”)
          printReverse(“”)
            return
        print “O”
      print “l”
    print “l”
  print “e”
print “h”

Here is the C++ code for the same

#include <iostream>

using namespace std;

void printReverse(char *str)
{
if( *str )
{
printReverse(str+1);
cout<<(*str);
}
}
int main()
{
char str[] = "reverse this";
printReverse(str);
return 0;
}

Program to generate all permutations of a given string

This is one of the famous programming problems. In this post, we discuss an algorithm to generate all permutations of a given array and how to implement the same in Java.This is also one of the beautiful example to understand recursion.

We discuss a recursive algorithm as it is simple to understand and implement. Let us define this problem in terms of itself. This is the first step in the process of forming a recursive solution.

Let us consider an array of length n. We can fix the first element (Observe that there are n possible ways) and try to generate permutations with the remaining (n-1) elements. Generating permutations of (n-1) elements is again the original problem, only with the smaller input size. Hence we can easily design  a recursive algorithm.

Here is how the algorithm works. Let us fix array[0] as the first element, and recursively find permutations for the remaining (n-1) elements. Next we will swap array[0] with array[1], and call the same function recursively for (n-1) elements and so on… for others( array[2], array[3],… array[n-1]). After every recursive call, we swap back the elements so that the original order is restored.

Let us understand this with a small example. The following is the recursion tree for a simple input array [1,2,3]. The elements marked in Red are the elements that are swapped.

Here is the Java implementation of the algorithm.

import java.util.Scanner;
public class Permutation {
public static void main(String[] args)
{
Scanner reader = new Scanner(System.in);
String input = reader.nextLine();
printPermutations(input.toCharArray(),0);
}
public static void printPermutations(char[] input,int start)
{
//Base case for recursion, if start index is the end;
//no need to recurse further, just print the pattern
if( start == input.length-1 )
{
for(int i = 0; i < input.length; i++)
System.out.print(input[i]);
System.out.println();
}
else
{
//fix the first character and generate per
for( int i = start; i < input.length; i++)
{
//swap start element, with ith element
if( i!= start) // swap only if start, and i are different
{
char t = input[start];
input[start] = input[i];
input[i] = t;
}

printPermutations(input,start+1);
//swap back the elements
if( i != start)
{
char t = input[start];
input[start] = input[i];
input[i] = t;
}
}
}
}
}