How to avoid StackOverFlow in recursion?

Question

I need to find the frequency of each character in a String using recursion. Found this question online and wanted to do this as a challenge.

Have used two variables 'a' and 'i', where 'a' is used to store the index of the current character in the string that needs to be searched and 'i' is used to go through the entire string in search of the character that 'a' has extracted.

Finding the frequency of each character present in the word.

import java.util.*;
public class ini {

    public static void main(String args[]) {
        recur(0, 0, "Hello how are you", 0);
    }

    static private char m = ' ';

    private static boolean recur(int a, int i, String s, int count) {
        if (s.length() >= 1) {
            if (a < s.length()) {
                m = s.charAt(a);
                if (i < s.length()) {
                    if (s.charAt(a) == s.charAt(i)) {
                        count += 1;
                    }
                    recur(a, ++i, s, count);
                }
                i = 0;
                System.out.println(s.charAt(a) + ":" + count);
                s = s.replaceAll(Character.toString(s.charAt(a)), "");
                a += 1;
                count = 0;
            }
            if (a != s.length() - 1) {
                recur(a, i, s, count);
            }
        } else {
            return false;
        }
        return true;
    }
}

The current output ignores the letter "w" altogether

H:1
l:2
 :3
o:3
r:1
y:1
Exception in thread "main" java.lang.StackOverflowError
at ini.recur(ini.java:26)
at ini.recur(ini.java:26)
at ini.recur(ini.java:26)
at ini.recur(ini.java:26)
at ini.recur(ini.java:26)
at ini.recur(ini.java:26)
at ini.recur(ini.java:26)
at...

Answer 1

There are a couple of things that we don't know:

1. Should h and H be considered only one character?
2. Should you count the spaces? (Programmatically speaking, space is a character)
3. Do you need an improved solution?
4. Are you allowed to do manipulate the initial text?

Some observations:

1. You need to rename your variables better
2. You don't need the static field
3. You don't need the recursive function to be boolean
4. a is used only for the identification of the character, and the increment is not needed

Quick solution:

private static void recur(int startingIndex, int recursionIndex, String text, int count) {
    if (text.length() >= 1) {
        if (startingIndex < text.length()) {

            char currentCharacter = text.charAt(startingIndex);

            if (recursionIndex < text.length()) {
                if (currentCharacter == text.charAt(recursionIndex)) {
                    count += 1;
                }

                recur(startingIndex, ++recursionIndex, text, count);
            } else {
                System.out.println(currentCharacter + ":" + count);
                text = text.replace(Character.toString(currentCharacter), "");

                recur(0, 0, text, 0);
            }
        }
    }
}

Improved solution:

public class Main {
    public static void main(String[] args) {
        recur(0, "Hello how are you", 0);
    }

    private static void recur(int index, String text, int count) {
        if (text.length() >= 1) {
            char currentCharacter = text.charAt(0);

            if (index< text.length()) {
                if (currentCharacter == text.charAt(index)) {
                    count += 1;
                }

                recur(++index, text, count);
            } else {
                System.out.println(currentCharacter + ":" + count);
                text = text.replace(Character.toString(currentCharacter), "");

                recur(0, text, 0);
            }
        }
    }
}

The optimal solution without modifying the initial text:

private static int recur(char character, String text, int index) {
    if (index >= text.length()) {
        return 0;
    }

    int count = text.charAt(index) == character? 1 : 0;
    return count + recur(text, character, index + 1);
}

Answer 2

After much tinkering I've figured it out. Basically you should not increment a. This will skip over letters and thus remove the line where a is incremented.a += 1; Furthermore, with recursion (I was struggling to remember myself) you want to be careful how you call the function you are in. If you don't make the recursive call as the last step (tail recursion), you will enter an infinite loop for various reasons here. All you need to do is add a return statement before the first recursive call and you will have solved it like so.

import java.util.*;
public class ini {

    public static void main(String args[]) {
        recur(0, 0, "Hello how are you", 0);
    }

    static private char m = ' ';

    private static boolean recur(int a, int i, String s, int count) {
        if (s.length() >= 1) {
            if (a < s.length()) {
                m = s.charAt(a);
                if (i < s.length()) {
                    if (s.charAt(a) == s.charAt(i)) {
                        count += 1;
                    }
                    //Added crucial return statement
                    return recur(a, ++i, s, count);
                }
                i = 0;
                System.out.println(s.charAt(a) + ":" + count);
                s = s.replaceAll(Character.toString(s.charAt(a)), "");
                //removed a += 1;
                count = 0;
            }
            if (a != s.length() - 1) {
                recur(a, i, s, count);
            }
        } else {
            return false;
        }
        return true;
    }
}

Output :

H:1
e:2
l:2
o:3
 :3
h:1
w:1
a:1
r:1
y:1

Here is a link about tail vs. head recursion : Tail vs. Head Recursion

Hope this helps you!

Answer 3

My approach is slightly different from yours but you might find it interesting. In my approach I am removing the character and checking the difference in the length of String. The change in length would be the times that character repeated. Rest is explained in the code.

public class CharactersFrequency {

    public static void main(String[] args) {
        CharactersFrequency cF = new CharactersFrequency();
        long startTime = System.currentTimeMillis();
        // I generated a sting with 1000 characters from a website
        cF.frequencyOfCharacters("a quick brown fox jumps over the lazy dog");
        long endTime = System.currentTimeMillis();
        System.out.println("Runtime: " + (endTime - startTime) + " ms");
    }

    private void frequencyOfCharacters(String input) {
        CharactersFrequency cF = new CharactersFrequency();
        cF.frequencyOfCharactersRec(input, input.charAt(0) + "");
    }

    public void frequencyOfCharactersRec(String input, String currentChar) {
        // If only one char is left
        if (input.length() <= 1) {
            System.out.println(currentChar + ": 1");
        } else {
            // Checking Initial length and saving it
            int inputOldLength = input.length();
            // Removing the char whose frequency I am checking
            input = input.replace(currentChar, "");
            // Checking new length
            int inputNewLength = input.length();
            // The difference between length should be the number of times that char 
            // repeated
            System.out.println(currentChar + " : " + (inputOldLength - inputNewLength));
            // In some cases after replace function the string becomes empty
            // thus charAt(0) gives an error
            if (inputNewLength > 0) {
                frequencyOfCharactersRec(input, input.charAt(0) + "");
            }
        }
    }
}

Output:

a : 2
  : 8
q : 1
u : 2
i : 1
c : 1
k : 1
b : 1
r : 2
o : 4
w : 1
n : 1
f : 1
x : 1
j : 1
m : 1
p : 1
s : 1
v : 1
e : 2
t : 1
h : 1
l : 1
z : 1
y : 1
d : 1
g: 1
Runtime: 3 ms