combining strings using recursion

Question

So I'm having a little trouble with the final part of my assignment on recursion. The method needs to use recursion to return a string that is formed from "weaving" together two strings taken in as parameters. For example:

weave("aaaa", "bbbb") // should return the string "abababab"
weave("hello", "world") // should return the string "hweolrllod"
weave("recurse", "NOW") // should return the string "rNeOcWurse"

Note that the extra characters from the first string—the characters in "urse"—come after the characters that have been woven together.

The important (and annoying) thing is that I'm not allowed to use any iteration loops (for, while, do while).

Here is my code thus far:

public static String weave(String str1, String str2)
{
    String word = str1 + str2;
    if(str1 == null || str1.equals("") || str2 == null || str2.equals(""))
    {
        return word;
    }              
    String word1 = weave(str1.substring(0, str1.length() - 1), str2.substring(0, str2.length() - 1));
    System.out.println(word1);
    return word;
}

For (Hello, World), my output is:

HW
HeWo
HelWor
HellWorl
HelloWorld

Obviously my characters aren't weaving, so I'm not sure what to do! Also, as stated above, the method should do not printing. I just added in the println statement as a test to see where my program was at.

@LiviuT. They do state the expected end result at the beginning in the examples. — Andrew Marshall
– Andrew Marshall, Commented Apr 3, 2012 at 18:22
Try using a private helper function, with a third parameter. — bvulaj
– bvulaj, Commented Apr 3, 2012 at 18:27
I think my brain froze when I read the question :) sorry about that — Liviu T.
– Liviu T., Commented Apr 3, 2012 at 21:11

Alexander · Accepted Answer · 2012-04-03 18:47:10Z

5

I think something like the following might work.

public String weave(String str1, String str2)
{
  if(str1.isEmpty() || str2.isEmpty()) {
    return str1 + str2;
  }
  return str1.substring(0, 1) + str2.substring(0, 1) + weave(str1.substring(1), str2.substring(1));
}

The idea is pretty simple: you only need to pop the first character from both input strings and concatenate both characters and the returned value from calling the function recursively with the stripped input strings until one of the input strings is empty in such case you should merely return the non-empty string.

weave("abcdef", "12"): "a" + "1" + weave("bcdef", "2")
  |
  +- weave("bcdef", "2"): "b" + "2" + weave("cdef", "")
       |
       +- weave("cdef", ""): "cdef"

Resulting in:

weave("abcdef", "12"): "a" + "1" + "b" + "2" + "cdef": "a1b2cdef"

edited Apr 3, 2012 at 18:47

answered Apr 3, 2012 at 18:31

Alexander

23.5k11 gold badges65 silver badges74 bronze badges

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

Comments

evanwong · Accepted Answer · 2012-04-03 18:35:33Z

0

The problem with your code is:

String word = str1 + str2;
//...
return word;

No matter how the recursive call, at the end it just return the result from the first method call when you pass in "hello", "world".

String word = str1 + str2; //hello + world
//... other things and the recursive call doesn't matter
//return word; //return the first word variable which is helloworld

answered Apr 3, 2012 at 18:35

evanwong

5,1543 gold badges34 silver badges45 bronze badges

Collectives™ on Stack Overflow

combining strings using recursion

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related