Odd/curious behaviour in a recursive function

Question

I am trying to program a function checking whether or not a string is the result of set of actions on previous string. Specifically, a string 'b' is a transformation of string 'a' if it follows the same order of characters, has only the same characters, yet may have them multiplied. For example: "aabba" is a transformation of "aba" however not of "abaa", as that has double 'a' at the end.

The code is as follows:

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

The program doesn't work as intended. Now here is the curious thing: running it through the debugger, it does everything as intended, however, when it reaches the "return (i+1)" command, instead of actually returning it, it starts to execute the recursive calls for some reason, meanwhile decreasing the value of i, until it reaches 0, and only then returning it, causing false negatives. More specifically, it goes up the stack and 'executes' the recursive calls of isTrans(s,i,t,j).

I would like to know why it does that, even more than a way to solve such a problem. It doesn't even enters through the iff's, but immediately enters the recursive calls, reducing the value of i all the way to 0 and only then returning it.

Appreciate any comments!

Edit: to clarify what exactly it does, according to the debugger. If I try to see if "aabba" is a transformation of "aba" (it is under the definitions above), the program reaches the desired value for i - 2. However, it then reaches the command return (i+1), and suddenly returns to line 17 in the given code, then the next recursive call in the code, and back to it - all the meanwhile reducing the value of i back to 0. Only then it executes the command outside of the function.

Edit 2: After a bit of tweaking and playing with the code, it seems that without connection to the return statement, at the end the function 'jumps' backwards, skipping through the 'if's, to the recursive calls - does not execute them, yet reduces i to 0 and only then continues. Does it have something to do with me calling isTrans(s,0,t,1)?

Answer 1

Your exit condition is return i+1. This will never work, even if your logic did, because the result you are returning is always one more than the length of the String.

Here is what likely happens in your code:

1. First if condition is satisfied
2. j is incremeanted.
3. Recursive call.
4. No more if conditions are satisfied, because i and j no longer point to the same letter.
5. It returns i+1

To do this recursively you would probably do something like this:

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

}

Hope you found it helpful.