递归函数中的奇怪/奇怪行为

学生数学

我正在尝试对一个函数进行编程,以检查字符串是否是前一个字符串上的一组操作的结果。具体来说,字符串“ b”是字符串“ a”的变换,如果它遵循相同的字符顺序,仅具有相同的字符,但可能会将它们相乘。例如:"aabba"是的转换,"aba"但不是的转换"abaa",因为它'a'的末尾加倍

代码如下:

public static boolean isTrans(String s, String t)
{
    if(s.equals(t)){return true;} //obviously the latter is transformation
    else if(s.length()==0||t.length()==0){return false;} //either is empty, can't be transformation
    else if(s.charAt(0)!=t.charAt(0)){return false;} //obviously not transformation
    else {return (s.length()==(isTrans(s,0,t,1)));} //recursive method below, note s.charAt(0)==t.charAt(0).
}
private static int isTrans(String s, int i, String t, int j)
{
    if(i < s.length() && j < t.length()) //only as long as the indexes are within right bound
    {
        if(s.charAt(i) == t.charAt(j)) //character at 'transformed' string is the character at original string
        {
            if((j+1)<t.length()) //only as long as there are more characters
            {
                j++;
                isTrans(s,i,t,j); //check next character at transformed string
            }
        }
        else if((i+1)<s.length()) //ensures there is a next character at string s
        {
            if(s.charAt(i+1) == t.charAt(j)) //character is the next chracter at original string
            {
                i++;
                if((j+1)<t.length()) //only as long as there are more characters
                {
                    j++;
                    isTrans(s,i,t,j); //checks next characters at strings
                }
            }
            else{i=-1;} //not transformation
        }
        else{i=-1;} //not transformation
    }    
    return (i+1);
}

该程序无法正常运行。现在这很奇怪:通过调试器运行它,可以按预期执行所有操作,但是,当到达“ return (i+1)”命令时,它实际上不是出于返回原因而开始执行递归调用,而实际上是将其返回,而是减小了该值的i,直到它到达0,然后才返回它,造成假阴性。更具体地说,它进入堆栈并“执行”的递归调用isTrans(s,i,t,j)

我想知道为什么会这样做,这不仅是解决此类问题的方法。它甚至不通过iff进入,而是立即进入递归调用,将i所有值减小为0,然后才返回。

感谢任何评论!

编辑:根据调试器,弄清楚它的确切作用。如果我尝试看看是否"aabba"是一个转型"aba"(这是上面的定义下),该程序为达到所期望的价值i- 2但是,它随后到达命令return (i+1),并突然返回给定代码中的第17行,然后返回该代码中的下一个递归调用,然后返回到它-同时减小iback的值0只有这样,它才能在函数外部执行命令。

编辑2:经过一些调整和使用代码后,似乎没有连接到return语句,最后函数“向后跳转”,跳过了“ if”,然后递归调用-不执行它们,但减少i0,然后才继续。它与调用isTrans(s,0,t,1)有什么关系吗?

米克尔·洛克(MikkelLøkke)

您的退出条件为return i+1即使您的逻辑做到了,这也永远不会起作用,因为您返回的结果总是比String的长度大一。

这是您的代码中可能发生的情况:

  1. 首先,如果条件满足
  2. j被激怒。
  3. 递归调用。
  4. 如果满足条件则不再需要,因为i和j不再指向同一字母。
  5. 返回i + 1

为此,您可能需要执行以下操作:

public class Main {
    public static void main(String args[])
    {
        String s = "aba";
        String t = "abz";
        System.out.println(isTrans(0, 0, s, t));
    }

    public static boolean isTrans(int si, int ti,String s ,String t)
    {
        // we have run out of source characters, or the source character has passed the transformation character. This is not a transformation.
        if (si > ti || si == s.length())
        {
            return false;
        }

        // we are at the end of the transformation string. This might be a transformation.
        if(ti == t.length())
        {
            return si == s.length()-1; // If we're at the end of our source string, otherwise it isn't.
        }

        // if the current positions contain identical characters...
        if (checkChar(si, ti, s, t))
        {
            // advance the transformation index.
            ti++; 
        }
        else
        {
            // otherwise, advance the source index.
            si++;
        }

        // recursion.
        return isTrans(si, ti, s, t);
    }

    private static boolean checkChar(int si, int ti, String s, String t)
    {
        return  (s.charAt(si) == t.charAt(ti));
    }

}

希望对您有所帮助。

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章