Simple recursion code wrong return

Question

Why does my code which should return true, return false?

The method isSubstring should return true if str2 contains zero or more characters, then all the characters of str1, then zero or more characters. The method should return false if a does not appear anywhere in b.

I am not looking for an alternative way to return correct output, but want to find out why my code is wrong.

public class stringRecursionPractice{
    public static void main(String[] args){
        String str1 = "abc"; 
        String str2 = "abc";
        System.out.println(isSubstring(str1, str2));
    }

    /*
     * Returns the string containing only the first character of the
     * specified string.
     */
    public static String head(String s) {
        return s.substring(0, 1);
    }

    /*
     * Returns the string containing the all the characters but the first
     * character in the specified string.
     */
    public static String tail(String s) {
        return s.substring(1);
    }

    public static boolean isSubstring(String str1, String str2){
    if(str1.length() == 1 && str1.charAt(0) == str2.charAt(0)){
        return true; 
    }

    if(head(str1).equals(head(str2))){
        isSubstring(tail(str1), tail(str2)); 
    }

    return false; 
    }
}

I have tried debugging it several times, but it keeps returning false. — CMSC
– CMSC, Commented Jul 26, 2015 at 2:35
Second if block, should also contains some return` statement, since in the absence of that, the control always goes to the last return false;. — nIcE cOw
– nIcE cOw, Commented Jul 26, 2015 at 2:36
But wouldn't the last recursive call isSubstring("c", "c") return true anyways? — CMSC
– CMSC, Commented Jul 26, 2015 at 2:38

Don Roby · Accepted Answer · 2015-07-26 02:35:27Z

3

Your recursive call should return the result:

if(head(str1).equals(head(str2))){
    return isSubstring(tail(str1), tail(str2)); 
}

answered Jul 26, 2015 at 2:35

Don Roby

41.2k6 gold badges95 silver badges114 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

CMSC Over a year ago

But wouldn't the last recursive call isSubstring("c", "c") return true anyways?

Tom Over a year ago

@CMSC Yes, it might return true, but you ignore that, so your program reaches the last statement of the isSubstring which is return false;. (the very first isSubstring call reaches that statement)

CMSC Over a year ago

@Tom Why does it ignore? The very first isSubstring call would get caught in the second if statement if(head(str1).equals(head(str2))). From there it would do recursion until str1 = "c" and str2 ="c". Then it would be caught in the first if statement and return 'true', shouldn't it?

Tom Over a year ago

@CMSC And then what? That very first call has done his job calling the isSubstring a second time ... and then? Since you haven't told him to return the result of the recursive call it just keeps executing the method, so it executes the statement return false.

CMSC Over a year ago

@Tom Oh I see. Thanks so much.

Collectives™ on Stack Overflow

Simple recursion code wrong return

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related