public class Substring {
    public static boolean isSubstring( String s1, String s2 ) {
        // Base Case 1:  if s1 is shorter than s2 return false
        if ( s1.length() < s2.length() )
            return false;

        // Path 1:  s1 starts with the string s2
        if ( subStringsAreEqual( s1, s2 ) )
                return true;

        // Path 2: Remove first char of s1 and see if s2 is a substring of the new s1
        return isSubstring( s1.substring( 1 ), s2 );
    }

    private static boolean subStringsAreEqual( String s1, String s2 ) {
        // Base case 2:  if s2 length equals 0 then s2 is a substring of s1
        if ( s2.length() == 0 )
            return true;

                // if the first half of the statement is false, the second half is not
                // evaluated due to the short circuiting of the && operator.
        return ( s1.charAt( 0 ) == s2.charAt( 0 ) )
                // Path 2:  if first char of s1 and s2 are equal, remove first
                // char and recurse to check next char
                && subStringsAreEqual( s1.substring( 1 ), s2.substring( 1 ) );
    }

    public static void main( String[] argv ) {
        String s1 = "substring", s2 = "string";

        System.out.println( Substring.isSubstring( s1, s2 ) );

        s1 = "hello";
        s2 = "hell";

        System.out.println( Substring.isSubstring( s1, s2 ) );

        s1 = "Madam";
        s2 = "ada";

        System.out.println( Substring.isSubstring( s1, s2 ) );

        s1 = "program";
        s2 = "pgram";

        System.out.println( Substring.isSubstring( s1, s2 ) );
    }
}