Skip to content
Advertisement

Coding Bat Recursion exercise (java)

How can I solve this problem recursively instead of using the replace method? I’m trying to get better a recursive methods.

Given a string, compute recursively (no loops) a new string where all the lowercase ‘x’ chars have been changed to ‘y’ chars.

changeXY("codex") → "codey"
changeXY("xxhixx") → "yyhiyy"
changeXY("xhixhix") → "yhiyhiy"

I cheated and solved it this way and tried to look at the source code for Java String method replace but I didn’t understand it. Here’s my method.

public String changeXY(String str) {
  int len = str.length();
  int i = 0;
  String changedStr = str.replace("x","y");


  if (len == 0)
    return str;

  return changedStr;

}

Any ideas on how to do it a recursive way?

Here’s a bonus exercise that I didn’t know how to do either. Thank you for your help!!!

Given a string, compute recursively a new string where all the ‘x’ chars have been removed.

noX("xaxb") → "ab"
noX("abc") → "abc"
noX("xx") → ""

Advertisement

Answer

Recursion is almost always composed of two things:

A condition to stop the recursion.

assuming we can solve a smaller problem, how to solve the current one using that assumption.

public String changeXY(String str) {

  // when to stop
  if (str.length() == 0){
    return str;
  }

  // handle the "special case" using an assumption we can solve str.substring(1)
  if (str.charAt(0) == 'x'){
    return 'y' + changeXY(str.substring(1));
  }
  // handle the "simple" case using an assumption we can solve str.substring(1)
  return str.charAt(0) + changeXY(str.substring(1));
}

Other exercises are very easy once you realize how this works.

User contributions licensed under: CC BY-SA
2 People found this is helpful
Advertisement