Print Alternating Characters From Two Strings (Interleaving) Using Recursion Java

Question

I'm trying to write a method that uses recursion to print the string formed by "interleaving" the strings str1 and str2. In other words, it should alternate characters from the two strings: the first character from str1, followed by the first character from str2, followed by the second character from str1, followed by the second character from str2, etc.

How would I go about this? Any ideas are greatly appreciated!! Thanks

Answer 1

This should work:

public String Interleave( String first, String second )
{
   if ( first.length() == 0 )
      return second;
   if ( second.length() == 0 )
      return first;
   return first.substring(0,1) + second.substring(0,1) +
      Interleave( first.substring(1), second.substring(1) );
}

Answer 2

The general idea of recursion is to have a terminating position that returns a constant value of some sort and then every other case is built on top of that.

For example, the factorial function, f(n) = n * (n-1) * (n-2) * ... * 2 * 1 has the following terminating condition and dependent functions:

f(1) = 1
f(n) = n * f(n-1) for all n > 1

so could be implemented as:

def factorial(n):
    if n == 1:
        return 1;
    return n * factorial(n-1)

In your particular case, the terminating condition is when either string is empty, at which point you just tack the other string onto the end. The dependent function is simply to grab the first character from the first string then call the next level down passing the rest of that string and the other string, but in reverse order so that you alternate.

def mix (s1, s2):
    if s1 == "" return s2
    if s2 == "" return s1
    return s1.firstChar() + mix (s2, s1.allButFirstChar());

In Java, this would translate to the following. Be warned that, if this is homework and you use this, you will almost certainly fail since you would be foolish to think your educators are not monitoring these sites.

public class Demo {
    public static String Mix (String s1, String s2) {
        if (s1.length() == 0) return s2;
        if (s2.length() == 0) return s1;
        return s1.substring(0,1) + Mix (s2, s1.substring(1));
    }
    public static void main(String[] args) {
        System.out.println (Mix ("Hello", "There"));
        System.out.println (Mix ("Hi", "There"));
        System.out.println (Mix ("Hello again", "Pax"));
        System.out.println (Mix ("", ""));
        System.out.println (Mix ("1111", ""));
        System.out.println (Mix ("111", "2"));
        System.out.println (Mix ("111", "22"));
        System.out.println (Mix ("111", "222"));
        System.out.println (Mix ("111", "2222"));
        System.out.println (Mix ("11", "2222"));
        System.out.println (Mix ("1", "2222"));
        System.out.println (Mix ("", "2222"));
    }
}

outputs:

HTehlelroe
HTihere
HPealxlo again

1111
1211
12121
121212
1212122
121222
12222
2222

Answer 3

This is the codingBat/String-2/mixString problem, except you want a recursive solution.

My solution is essentially the same as Kieveli's:

public String mixString(String a, String b) {
  return 
    a.isEmpty() ? b :
    b.isEmpty() ? a :
    a.substring(0, 1) + b.substring(0, 1)
      + mixString(a.substring(1), b.substring(1));
}