如何在递归中避免 StackOverFlow？

Question

我需要使用递归找到 String 中每个字符的出现频率。在网上发现了这个问题，并想以此作为挑战。

使用了'a'和'i'两个变量，其中'a'用于存放当前字符在需要查找的字符串中的索引，'i' 用于遍历整个字符串以搜索 'a' 提取的字符。

找出单词中出现的每个字符的频率。

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;
    }
}

当前输出完全忽略字母"w"

H:1
l:2
 :3
o:3
r:1
y:1
Exception in thread "main" java.lang.WhosebugError
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

经过多次修改，我已经弄明白了。基本上你不应该增加 a。这将跳过字母，从而删除递增 a 的行。a += 1; 此外，使用递归（我一直在努力记住自己）你要小心如何调用你所在的函数。如果你不如果不把递归调用作为最后一步（尾递归），这里会因为各种原因进入死循环。您需要做的就是在第一次递归调用之前添加一个 return 语句，这样您就可以解决它。

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;
    }
}

输出：

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

这是关于尾递归与头递归的 link：Tail vs. Head Recursion

希望对您有所帮助！

Answer 2

有几件事我们不知道：

h和H应该只算一个字符吗？
你应该数 space 吗？（从程序上讲，space是一个字符）
您需要改进的解决方案吗？
您可以对初始文本进行操作吗？

一些观察：

您需要更好地重命名变量
您不需要静态字段
你不需要递归函数是布尔值
a仅用于字符的识别，不需要自增

快速解决方案：

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);
            }
        }
    }
}

改进的解决方案：

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);
            }
        }
    }
}

不修改初始文本的最优解：

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 3

我的方法与您的略有不同，但您可能会发现它很有趣。在我的方法中，我将删除字符并检查字符串长度的差异。长度的变化将是字符重复的次数。其余部分在代码中解释。

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) + "");
            }
        }
    }
}

输出：

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

如何在递归中避免 StackOverFlow？

How to avoid StackOverFlow in recursion?

java

stack-overflow

recursion

exception