Double each occurrence of a char recursively

Question

The exercise is to write a recursive method that takes a String and a char parameter and returns a String with each occurrence of the char doubled. Additionally, the number of doubling operations should be added at the end of the string. No "extern" variables outside the method are allowed to use. The String parameter can contain any valid char, including numbers.

My code works up to 1000 doubling operations, but not correctly for 1001. My question is whether this is just a rounding error or whether this task is theoretical unsolvable.

public class Doubly {
 public static String doubly(final String s, final char c) {
 if (s.length() > 0) {
 if (c == s.charAt(0)) {
 int len1 = s.length();
 String s1 = "" + c + c + doubly(s.substring(1), c);
 int len2 = s1.length();
 int lenDiff = len2 - len1;
 int log = (int) Math.log10(lenDiff - Math.log(lenDiff + 1) + 1) + 1;
 if (log > 0) {
 int n = Integer.parseInt(s1.substring(s1.length() - log));
 return s1.substring(0, s1.length() - log) + (n + 1);
 }
 return s1;
 }
 return "" + s.charAt(0) + doubly(s.substring(1), c);
 }
 return "0";
 }
 public static void main(final String[] args) {
 String s = "ccc";
 for (int i = 0; i < 1500; i++) {
 s += "a";
 String s2 = doubly(s, 'a');
 System.out.println("Expected: " + (i + 1) + ", actual: " + s2.substring(s2.length() - (int) Math.log10(i + 1) - 1));
 if (!String.valueOf(i + 1)
 .equals(s2.substring(s2.length() - (int) Math.log10(i + 1) - 1))) {
 System.out.println("ERROR");
 return;
 }
 }
 }
}

Answer 1

typo

Wow, you really like that log10 expression. I see several occurrences of it. Might be worth packaging up in a helper function. Which you could unit test.

I don't understand this expression at all:

 int log = (int) Math.log10(lenDiff - Math.log(lenDiff + 1) + 1) + 1;

You say the code works correctly, but how is natural log relevant? Or is that just a typo bug?

Recall that examining length of Integer.toString(n) is another way to learn its base-ten logarithm. (My initial theory was the bug was due to FP rounding issues, until I saw natural log working its way into the mix. Or perhaps a string length OBOB related to 99 -> 100 or 999 -> 1000.)

recursive function that iterates

You embrace recursion fully with this test:

 if (c == s.charAt(0)) {

So the (non-empty) base case is a test for: "Starts with c?"

Another approach would have been to examine s.indexOf(c), which iterates until hitting either a match or end-of-string. A -1 says there's no more recursing to do. Else we turn a "FRONT c BACK" string into "FRONT cc BACK".

data format

You're passing around "ccccNN", along with an integer, the string length. And you're finding it a bit of a challenge both to get that format right, and to debug it when things go south. Recommend you adopt a simpler format.

At the outset you might try sample delimiters, such as SPACE or ↑ or 气, till you find one that is not present in s. Pass it around as a parameter during recursive calls. Then your format is "cccc NN", and s.reverseIndexOf(' ') lets you split apart string from the serialized count. Hmmm, actually you can always use SPACE, even if it occurred in s, just ensure the first call tacks on a " 0" suffix to get things started, and maybe strip it at the end if necessary.

Alternatively, rather than a single String you might choose to pass around a Map.Entry(s, n) pair, which is how standard java offers Pair.of(s, n) from Apache Commons. Take care to nicely format the string at the end when recursion is done.

---

This codebase is buggy and does not achieve its design goals.

Given the peculiar representation of an integer, and the lack of a test suite, I would not be willing to delegate or accept maintenance tasks on it.

• Tobias Grothe: Thanks! The natural log was a problem. I found out, that i have to solve floor(x*2+log_10(x)+1) for x, see here. In simply words: This allows me to reconstruct how many times it was doubled.