Is this creating 12 string objects?

Question

I'm trying to understand if this code below creates 12 objects for a string like "stephan"

public String reverse(String str) {
            if ((null == str) || (str.length()  <= 1)) {
                return str;
            }
            return reverse(str.substring(1)) + str.charAt(0);
        }

This recursively reverses a string. I understand how it works. But I was thinking if there is a relationship in this case between the length of the strings and number of string objects created through concatenation?

substring() will create a String object. The + will create another one. I don't know what you mean by a relationship to the length of the string, though. — Marvo, Aug 29 '12 at 00:30
@Marvo - his function is recursive. So that count will happen once per character on each recursive call — DVK, Aug 29 '12 at 00:37
substring does not create a string, it returns a view to the original string - the + however does. — Amir Afghani, Aug 29 '12 at 00:47
I realize it's recursive. I was pointing out where in the code Strings are created. The input would determine the final count. — Marvo, Aug 29 '12 at 01:36
@Amir Afghani: JDK 1.6 source code claims to return a `new String` (see below). — EthanB, Aug 29 '12 at 01:36
This answer http://stackoverflow.com/questions/704319/how-the-substring-function-of-string-class-works indicates that while some implementations may re-use the backing character buffer when performing substring, a new String object is created in the heap. — Marvo, Aug 29 '12 at 01:39
From String.substring: `return new String(offset + beginIndex, endIndex - beginIndex, value);`. So, yes the char-array (value) is re-used. — EthanB, Aug 29 '12 at 01:42

DVK · Accepted Answer · 2012-08-29T00:38:48.373

2

Yes, it will create tons of string objects.

Every recursive call to "reverse()" will create 2:

str.substring(1) will create a new String object
reverse() call will create a new string for its return value, but we will NOT count that since that's counted when analyzing that recursive call (e.g. it will be the string from bullet point #3 from the next reverse() call).
And since Java Strings are immutable, adding a char via "+" will create a second String object.

Therefore, for a string of length N, it will create (N-1)*2 objects (since a reverse of 1-char string does NOT create new strings); so for "stephan"'s 7 characters, it will create 6*2=12 string objects.

edited Aug 29 '12 at 00:38

answered Aug 29 '12 at 00:30

DVK

126,886
32
213
327

So will charAt(0) which returns a char also be converted to a string before concatenation ? – Phoenix Aug 29 '12 at 00:33
Don't forget the StringBuilders created to actually concatenate each intermediate result and the next char. – EthanB Aug 29 '12 at 00:33
@Phoenix: No, characters aren't converted to strings, the byte-code will look something like `new StringBuilder().append(string).append(char).toString();` – EthanB Aug 29 '12 at 00:35
@EthanB - StringBuilder doesn't count as a String object, no? Mind you, as far as resource allocation it's still an object; but the OP explicitly asked about strings – DVK Aug 29 '12 at 00:35
@DVK Nope. It's used for the concatenation. (OP probably doesn't know about the byte-code.) – EthanB Aug 29 '12 at 00:35
So the first call is (tephan) + s .. FOr this one alone will it be counted as 2 OR 3 objects ? 1 for whatever is the return value from (tephan) and one for "s" and one for the concatenation result ? What I am reading from the previous comments is the char will not be converted to "s" so this means only 2 will be created – Phoenix Aug 29 '12 at 00:40
@Phoenix: "tephan" (1) and the string-builder to append the "s" (2), and the reversed result (3). Individual chars don't count. – EthanB Aug 29 '12 at 00:44
@EthanB how is it 12 then ? if for every call 3 are being created except the last one ? – Phoenix Aug 29 '12 at 00:46
@Phoenix - because StringBuilder is not a String. it's 12 Strings and 18 objects – DVK Aug 29 '12 at 00:53
@DVK - but they're all `CharSequence`s! ;) – EthanB Aug 29 '12 at 01:39

EthanB · Answer 2 · 2012-08-29T01:36:28.630

Theorem:

When a string is N characters long, @Phoenix's reverse implementation will create (N-1)*3 new objects.

Proof (by induction):

When str is 1 character long, it is returned directly. (1*1)*3 = 0.
When str is N characters long:
- a new String will be created by .substring(1).
- by the induction hypothesis, the call to reverse(...) will be returned after (N-2)*3 objects have been created.
- a new StringBuilder will be created to append the string and first char (you can see this by de-compiling your byte-code).
- a new String will be created by StringBuilder.toString()--this is the return value.
- Altogether, there were 3 + (N-2)*3 = (N-2 + 1)*3 = (N-1)*3 objects created.
QED.

[Edit] StringBuilders:

StringBuilder (extending AbstractStringBuilder) does its own fancy footwork:
- When an StringBuilder is constructed, it is initialized with a char[] of size 16.
- When you append something more than it's present size, it throws that away and creates a new char[] of size (<old size> + <size of new data> + 1) * 2.
So, as soon as your input string is > 16 characters, you have essentially 2x as much StringBuilder capacity as you need. (When the input string size is less, you've got more char[] than you need.)
Considering Strings are essentially char[]s (with a few ints for good measure), you're effectively using 4 times the length of the substring in char[]s -- at each step. :(

Is this creating 12 string objects?

2 Answers2