Reinterpreting a string, treating < as a backspace character

Question

I've come up with a solution to this coding challenge using recursion. In summary, the input is a string where the < symbol represents a backspace (up to 1 million characters). The output should be a string where all characters that come before a backspace or series of backspaces are removed, as well as the backspaces themselves. E.g.:

"a<bc<"        --> "b"
"foss<<rritun" --> "forritun"

Here is my solution to the problem, in Java:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String broken_str = scanner.nextLine();
        System.out.println(fix(broken_str));
    }

    public static String fix(String broken_str) {       
        int brack_idx = broken_str.indexOf('<'); // index of the first occurrence of '<'
        if (brack_idx < 0) {
            // if '<' isn't found then the string is fixed
            return broken_str; 
        }

        int num_brax = 0; // keeps track of the number of brackets in the current sequence
        while (brack_idx < broken_str.length() && broken_str.charAt(brack_idx) == '<') {
            ++num_brax; ++brack_idx;
        }

        return broken_str.substring(0, brack_idx - 2 * num_brax) // this substring ranges up to the first character that should be removed
                + fix(broken_str.substring(brack_idx)); // this substring is from the index after the last occurrence of '<' until the end of the string
    }

}

This algorithm passes for the first three test cases, but the fourth one results in a runtime error. I've tried to create test cases of my own, and when the string is really long, I get a stack overflow. I was wondering if the algorithm can be optimized.

By the way, I know that this can be done very easily iteratively, but that's kind of boring. If this can only be made efficient iteratively then let me know.

Answer 1

Recursion is a great tool to have available when dealing with some problems, but each recursive call carries a cost. The cost depends on the language being used, and perhaps the OS architecture. As a consequence, the usefulness of recursion is limited by the circumstances in which the recursion is applied.

In Java each function call typically costs a number of kilobytes of memory as that's the size of the stack frame (and each call requires a new stack frame). Also, in Java, the stack size (memory) is pre-allocated as part of the VM settings (see -Xss commandline option) Other languages (for example, Go) have a much cheaper mechanism for stack management, and thus the cost of recursion is reduced. Java typically cannot go further than a few thousand calls deep in the stack, Go can go millions of calls deep. In your use case, the depth of the stack is proportional to the length of the input string, and strings longer than a few thousand characters will cause an out-of-memory problem.

Bottom line, is that recursion is not the solution to use for your problem. Even in other more stack-friendly languages I would still avoid recursion.

Solve it iteratively, using a StringBuilder, a Reader, and an if-statement...

public static String fix(Reader reader) {
    int ch;
    StringBuilder result = new StringBuilder();
    while ((ch = reader.read()) >= 0) {
        if (ch == '<') {
            result.setLength(result.getLength() - 1);
        } else {
            result.append((char)ch);
        }
    }
    return result.toString();
}