Recursion

This is a simple concept and yet scares many, as a simple mistake can bring down even a supercomputer by making infinite recursive calls and run out of resources. Also it is hard to think recursively as we can’t easily relate to any of the real world elements. It is not too complex topic to understand like 5th dimension and by the way, the dimensions topic is pretty interesting too.

Why should I learn recursion?

It is one of the key concepts and following are some of the algorithms and problem spaces which we can easily solve using recursion –

• Divide and Concur – Ex: Merge Sort
• Backtracking
• Dynamic Programming (a few)
• Graphs & Tree problems
• Linked List problems
• Permutations & Combinations
• Solving games  – like Maze, Sudoku etc

Hoping now that you are motivated to understand recursion lets start by discussing an example.

What is recursion?

Let us assume you bought a box of chocolates to a classroom and want to give it to everyone in the class. One intuitive and simple way is to go to each person and give a chocolate. This will surely make us work hard and more the members in classroom the more work we do. Is there a better way?
What about, you take a chocolate for yourself and give the box to the person next to you and say, can you take one and pass on to the next person? He simply can take one chocolate for himself and then do the same thing – giving it to next person.
Above problem can be classified as recursion – distributing chocolates. Taking a chocolate is doing some work and then simply recurse for remaining persons in the classroom. One of the important thing is, this will stop when everyone gets a chocolate. By the way, this is called the base case.
Following are the two important things to remember when we write recursive functions,

• It should contain a base case. That means, we should have a small enough problem where we can solve it directly and simply stop recursing further. In above example, last person simply takes the chocolate for himself and stops as everybody already got one.
• The problem should become smaller and smaller for each recursive call. In the above example, first we need to give it to all and next it is all-1, all-2, all-3 and so on.

Let us look at the simple programming example – print “Hello World!” 10 times.
The intuitive way is, loop through 10 times and print the statement “Hello World!” but assume that we have a constraint of not to use loop construct. What about, we print “Hello World!” and then recursively say, can you print 9 more times, print and recurse for 8 more times, print and recurse 7 more times and so on till we reach printing only 1 time. This can be written as follows,

    public static void printHelloWorld(int times) {
        if (times == 0) {
            return; // base case
        } else {
            System.out.println("Hello World!");
            printHelloWorld(times - 1); // recursive call
        }
    }

The above can also be written simply as,

    // implicit base case
    public static void printHelloWorld(int times) {
        if (times > 0) {
            System.out.println("Hello World!");
            printHelloWorld(times - 1); // recursive call
        }
    }

The best way to get comfortable with this topic is to solve as many recursive problems as possible. Let us look into some of the problems below and see how can we solve them with recursion.

POW function

Given a base and exponent, how do we raise the wbase to the given exponent. Iteratively, we can solve this by simply using a loop construct and multiply base exponent times. Can we do this recursively? Let us take an example – base is 2 and exponent is 10. This can also be written as 2 * (2 raised to 9). So that means, if we know the value of base raised to (exponent – 1) times, then we can simply multiply it with base once and we get what we want. If you look at this approach carefully, raising base to (exponent – 1) times is same problem and so we can easily form this into recursive formula – base raise to exponent  =  base * (base raised to exponent -1). That is pow(base, exponent) = base * pow (base, exponent -1). The base case occurs when exponent is 0 and in that case, we simply return 1. Following is the java code,

    public static double pow(double base, double power) {
        if (power <= 0) {
            return 1.0;
        } else {
            return base * pow(base, power - 1);
        }
    }

Recursive call stack for POW function

A visual way to look at the above is for – raise 2 to 5,

Just FYI, if you carefully observe it, we can do little optimization and reduce the run time of the above from O(n) to O(log n). The recursive formula can also be written as,

• If exponent is even, then pow(base, exponent) = pow(base, exponent/2) * pow(base, exponent/2)
• if exponent is odd, then pow(base, exponent) = base * pow(base, exponent/2) * pow(base, exponent/2)

Optimized java code for POW function is,

    public static double power(double x, int n) {
        if (n == 0) {
            return 1;
        } else {
            double v = power(x, n / 2);
            if (n % 2 == 0) {
                return v * v;
            } else {
                return v * v * x;
            }
        }
    }

By the way, the above code does not work for negative exponents and you can take that as an exercise.
Hint – write a wrapper function to check if exponent is negative or positive and then I hope you know what to do.

Palindrome

Given a string input, find if it is a palindrome or not. As per Wikipedia – “A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward”. One other way to think of this is, take first and last character and compare. If they are equal then remove them and check for inner string. If at any point the first and last character is not same, it is not a palindrome otherwise it is. The recursive formula is,

• palindrome(INPUT) = (first character == last character ) and palindrome(INPUT after first and last characters removed)

The better way to understand is to visualize it.

Comparisons for “MADAM” word

Recursive call stack for “MADAM” palindrome method

Java code for implementing palindrome recursively is,

    public static boolean isPalindromeRecursively(String input) {
        if (input.length() <= 1) {
            // one character or zero characters string is palindrome.
            return true;
        } else {
            char firstChar = input.charAt(0);
            char lastChar = input.charAt(input.length() - 1);
            // both end chars are same and inner input is palindrome, then it is palindrome.
            return (firstChar == lastChar) && isPalindromeRecursively(input.substring(1, input.length() - 1));
        }
    }

Note,

• The above code is not efficient as it creates many substrings and the better way to write it by converting the input to array and use start and end indexes.
• It might have few more constraints like ignoring special characters and spaces. For example, “A man, a plan, a canal — Panama!” might be considered as a palindrome but above code returns false.

A good exercise for you would be to take the above constraints and write/modify the code.

Binary search

This is one of the best algorithms to know and can be written very easily using recursion. The problem is, we are given a list of sorted integers (for the sake of simplicity) and a number which we need to search for. The brute force algorithm is to simply scan the elements from start to finish and see if we have the number which we are searching for. We can take the advantage of the sorted property and do much better as follows.

• check the mid element
  • if it is the one which we are looking for then we are done
  • If not,
    • if it is greater than what we are looking for, then recursively search in the left half as all elements on right will be greater and there is no way we can find what we are looking for as the array is sorted
    • If it is less than what we are looking for, then search in the right half as all elements in the left half are smaller
  • if neither of the above are true then that element does not exist in this – not found.

Recursion – Binary Search comparisons

Following is the java code for binary search algorithm,

    public static int search(int[] input, int element, int start, int end) {
        if(end < start) return - 1;
        int mid = (start + end)/2;
        if(input[mid] == element) return mid;
        if(element < input[mid]) {
            return search(input, element, start, mid -1);
        } else {
            return search(input, element, mid + 1, end);
        }
    }

Summary

There are many different kinds of problems which we can resolve and most of them tend to following these patterns –

• Dive into half and recurse on left or right (sometimes both) half – like binary search
• Solve first/last and then recurse on remaining
• Choose one or make one decision and recurse on remaining one
• Recurse first and then process – like power function as we need the value from recursive call to calculate the current value
• Process and then recurse – like binary search and some of graph searching algorithms
• Bottom up vs Top down recursion
• Base case is important and also make sure every recursive call is made for smaller problem – otherwise we end up in infinite loop

Hope this blog gave you some insights on recursion and the best way to get comfortable with this is to practise as many problems as possible. Following are few other problems,

• N – Queens problems
• Towers of Hanoi
• Permutations of given input
• Edit distance – String similarity
• Knapsack
• Factorials
• Fibonacci numbers