Top down recursion without using stack

What this article has for you

Using top down style with recursion, without using stack memory, sounds like magic isn’t it?

This is something I have learned through experience by working on problems with large scale input. Top down approach in recursion is very intuitive, and no wonder preferred by most programmers, while on the other hand, bottom up approach can be a little hard to understand at first glance, but it trades stack memory with heap(which in most configurations is bigger than stack).

So what would you do, when you wrote a code in an intuitive top down style, but you started getting stack overflow errors, as your input scaled up.

Converting to bottom up style is one way of solving the problem, but i will show you a simple trick in this article, using which you can trade stack with heap in just a few lines of code.

Basic principle of Top Down

So, what is the basic principle of top down approach? Consider a simple problem of permutations. What all possible strings can you make from characters a, b and c?

The above tree is your answer, reading from left to right, your possible strings are: -

abc, acb, bac, bca, cab, cba

The basic principle of top down programming is:- by looking at the problem from top, what all possible choices can you make at each step before breaking the problem down.

So, by this principle we can say the first character in the string can be either a, b or c and then second character can be all the remaining characters, excluding the first choice you made, and so on.. until you run out of characters.

You traverse all of the possible choices and form a result.

Basic principle of Bottom up

The basic principle of bottom up approach is that you solve the problem by understanding the relation between the solution of smaller problem and bigger problem.

So start by asking yourself these questions?,

What is the solution if you have only one character ‘c’ ?

Can you build on that solution if you add another character b? and then another and so on?

The solution to first problem is:-

A single string “C” (if you only have one character ,’c’ you can only create one string)

The solution to second problem is: -

“bc”

“cb”

Did you see the relation/pattern? You take the character of bigger problem and insert before and after each character in the solution of smaller problem.

The same extends to when you add another character ‘a’ in the problem:-

Insert before and after each character in the solution of smaller problem (“bc”, “cb”) → “abc”, “bac”, “bca”, “acb”, “cab”, “cba”

So yo see we are building our answer from the very bottom rather than from the top.

The straight benefit is that the bottom up approach is not recursive and hence does not uses stack, but these approaches can get harder to understand and implement! So whats the sweet alternative?

The trick is to use recursion but build up the answer from the bottom.

Let me show that with the help of a simple java code to the above problem, but the language doesn’t matter.

public static void main(String[] args) {
    String possibleCharacters = "abc";
List<String> result =    
    getAllPossibleStringsRecursive(possibleCharacters);
    System.out.println(result);
}
public static List<String> getAllPossibleStringsRecursive(String possibleChars) {
    LinkedList<String> result = new LinkedList<>();
    if (possibleChars.length() == 1) {
        result.add(possibleChars);
        return result;
    }
    for (int i = 0; i < possibleChars.length(); i++) {
        char currentChar = possibleChars.charAt(i);
        String remainingString = possibleChars.substring(0, i) +  
        possibleChars.substring(i + 1);
        for (String possibleString :   
        getAllPossibleStringsRecursive(remainingString)) {
            result.add(currentChar + possibleString);
        }
    }
return result;
}

Above is a simple recursive code, that basically traverses all possible options at a given position and forms a response by depth first search, top down approach.

And, below is the iterative bottom up approach, where we build our response from the bottom:-

public static void main(String[] args) {
    String possibleCharacters = "abc";
    List<String> result =   
    getAllPossibleStringsIterative(possibleCharacters);
    System.out.println(result);
}
public static List<String> getAllPossibleStringsIterative(String possibleChars) {

    LinkedList<String> result = new LinkedList<>();
    
    for (int i = possibleChars.length() - 1; i >= 0; i--) {
        LinkedList<String> intermediateResultSet = 
        new LinkedList<>();
        if (result.isEmpty()) {
            intermediateResultSet.add(
                Character.toString(possibleChars.charAt(i))
            );
        } else {
            for (String intermediateResultString : result) {
                 for (int j = 0; j <=   
                     intermediateResultString.length(); j++) {
                     intermediateResultSet.add(
                         intermediateResultString.substring(0, j) 
                         + possibleChars.charAt(i)
                         + intermediateResultString.substring(j)
                     );
                 }
            }
       }
       result = intermediateResultSet;
    }
    return result;
}

Both runtimes are O(n²n!) but the top down approach uses stack memory instead of heap.

So, now we come to our question can we still use recursive style and trade off stack with heap??

Yes we can! we just have to memoize our recursive function and call it in a bottom up fashion.

public static void main(String[] args) {
    String possibleCharacters = "abc";
    Map<String, List<String>> memoryMapper = new HashMap<>();
    List<String> result = null;
    //Here is the magic line
    for (int i = possibleCharacters.length() -1 ; i >=0; i--) {
        result =   
        getAllPossibleStringsRecursive(
            possibleCharacters.substring(i),  
            memoryMapper
        );
    } 
    System.out.println(result);
}
public static List<String> getAllPossibleStringsRecursive(String possibleChars, Map<String, List<String>> memoryMapper) {

    if (memoryMapper.containsKey(possibleChars)) {
        return memoryMapper.get(possibleChars);
    }
    LinkedList<String> result = new LinkedList<>();
    if (possibleChars.length() == 1) {
        result.add(possibleChars);
        return result;
    }
    for (int i = 0; i < possibleChars.length(); i++) {
        char currentChar = possibleChars.charAt(i);
        String remainingString = possibleChars.substring(0, i) + 
        possibleChars.substring(i + 1);
        for (String possibleString :    
            getAllPossibleStringsRecursive(remainingString,    
            memoryMapper)) {
            result.add(currentChar + possibleString);
        }
    }
    memoryMapper.put(possibleChars, result);
    return result;
}

Notice how we first memoized our recursive function:-

if (memoryMapper.containsKey(possibleChars)) {
     return memoryMapper.get(possibleChars);
}

But here is the magic line, that prevents the recursive function to use stack memory.

for (int i = possibleCharacters.length() -1 ; i >=0; i--) {
result =   
        getAllPossibleStringsRecursive(
            possibleCharacters.substring(i),  
            memoryMapper
        );
}

We first call the recursive function with the last character ‘c’ and store results in a HashMap.

Then we call the recursive function with “bc” as remaining characters, it will trigger a recursive call with just “c” as remaining characters, but won’t go down further, as that answer is already available in our memoized HashMap.

Then we call the recursive function with “abc” as remaining characters, it will trigger a recursive call with just “bc” as remaining characters, but won’t go down further, as that answer is already available in our memoized HashMap.

So now we don’t have to sacrifice our intuitive recursive code, to trade stack memory with heap and scale up with our input. This is indeed sweet!