Recursion: insert \$ between each letter of a String

Page 1 of 1

10 Replies - 760 Views - Last Post: 16 August 2017 - 02:13 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=405746&amp;s=3af62d90f8c62342c596e356097e6ec9&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 Dewey Banks

Reputation: 0
• Posts: 28
• Joined: 03-June 17

Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 07:43 AM

With respect to the following code, I'm having difficulty understanding how it is that the string length is reduced with every recursive method invocation. ( The base case is string.length() <= 1 ). I'm hoping someone can explain this to me.

```public class Recursion {

public static void main(String[] args) {
// Recursion is a process of repeating items in a self-similar way.
// solve a problem by solving smaller instances of the same problem.
// inside a method we invoke the method

// method should have a condition for calling itself and stop when result obtained.
// method can return a value and call itself within the body of the method
// 1. make a base case if() else { do something... return call to itself }
// what chages is the argument that passes to every invocation.

System.out.println(allDollars("hello")); // h\$e\$l\$l\$o
System.out.println(allDollars("james"));
}

// us charAt() and substring()
private static String allDollars(String string) {
// set up our base case
if(string.length() <= 1) {
return string;
}

// return first character of the string plus \$
// string loses a letter with each method invocation
return string.charAt(0) + "\$" + allDollars(string.substring(1));

}
}

```

Thanks,
DB

Is This A Good Question/Topic? 0

Replies To: Recursion: insert \$ between each letter of a String

#2 Dewey Banks

Reputation: 0
• Posts: 28
• Joined: 03-June 17

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 08:02 AM

More specifically, I think my difficulty is in understanding how charAt(0) and substring(1) don't just return the same value over and over and over again. I think I understand the methods - I've used them before. But I just fail to see how the result is obtained here.

What if I wanted to change this to add %20 between each character? I couldn't use charAt(0) nor could I simply go "%20".... + all Dollars()...

This post has been edited by Dewey Banks: 12 August 2017 - 08:08 AM

#3 NormR

• D.I.C Lover

Reputation: 672
• Posts: 5,074
• Joined: 25-December 13

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 08:27 AM

Quote

how it is that the string length is reduced with every recursive method invocation

Think about what String is passed to the method using string.substring(1)

Doesn't that strip off the first character of the String each call?
string
tring
ring
ing
ng
g

This post has been edited by NormR: 12 August 2017 - 11:31 AM

#4 g00se

• D.I.C Lover

Reputation: 3515
• Posts: 15,901
• Joined: 20-September 08

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 10:31 AM

Quote

What if I wanted to change this to add %20 between each character? I couldn't use charAt(0) nor could I simply go "%20".... + all Dollars()...

Why not?

#5 Dewey Banks

Reputation: 0
• Posts: 28
• Joined: 03-June 17

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 01:12 PM

g00se, on 12 August 2017 - 10:31 AM, said:

Quote

What if I wanted to change this to add %20 between each character? I couldn't use charAt(0) nor could I simply go "%20".... + all Dollars()...

Why not?

Why not? Because charAt() expects a char. "%20" is a String. I thought of trying string.indexOf(0) = "%20" but this is not a legal because indexOf expects a string, not an index. Finally I considered replace, but the functions aren't set up to accept indices as arguments.

So I'm unsure how to progress..

This post has been edited by Dewey Banks: 12 August 2017 - 01:17 PM

#6 NormR

• D.I.C Lover

Reputation: 672
• Posts: 5,074
• Joined: 25-December 13

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 01:20 PM

Quote

Did you try it? What happened?

This post has been edited by NormR: 12 August 2017 - 01:21 PM

#7 Dewey Banks

Reputation: 0
• Posts: 28
• Joined: 03-June 17

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 01:31 PM

NormR, on 12 August 2017 - 01:20 PM, said:

Quote

Did you try it? What happened?

I think a better solution would be to use a loop and StringBuilder. However, I'll give both methods a shot and get back to you.

Plus, I overlooked a glaring logical error. In the previous code, the tempChar variable was being overwritten.

I believe the following is a better version:
```public static String makeComplement(String dna) {
StringBuilder tempStringBuilder = new StringBuilder();
for (int index = 0; index < dna.length(); index++) {
char tempChar = dna.charAt(index);
if (tempChar == 'A') {
tempChar = 'T';
} else {
if (tempChar == 'T') {
tempChar = 'A';
}

}

if (tempChar == 'C') {
tempChar = 'G';
} else {
if(tempChar == 'G') {
tempChar = 'C';
}
}
tempStringBuilder.append(tempChar);
}

return tempStringBuilder.toString();

}

```

The code works for my handful of tests but fails all of codewars'. And I don't understand why.

This post has been edited by Dewey Banks: 12 August 2017 - 01:45 PM

#8 Dewey Banks

Reputation: 0
• Posts: 28
• Joined: 03-June 17

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 01:46 PM

An even better version, of course, would use a switch

#9 NormR

• D.I.C Lover

Reputation: 672
• Posts: 5,074
• Joined: 25-December 13

Re: Recursion: insert \$ between each letter of a String

Posted 12 August 2017 - 02:03 PM

That looks like a new problem. You should start a new thread for a new problem.

#10 g00se

• D.I.C Lover

Reputation: 3515
• Posts: 15,901
• Joined: 20-September 08

Re: Recursion: insert \$ between each letter of a String

Posted 15 August 2017 - 12:53 AM

Quote

Why not? Because charAt() expects a char. "%20" is a String.

That observation reveals you haven't understood how the method works. Perhaps begin by changing "\$" to "%20" and working from there

#11 Arthur O Podd

Reputation: 0
• Posts: 19
• Joined: 29-July 17

Re: Recursion: insert \$ between each letter of a String

Posted 16 August 2017 - 02:13 PM

I am not sure I would use recursion for much other than amusement for this type of issue. The overhead can often outweigh the benefits. Loops would do the trick here. But here is one recursion for you.

```class Insert {

static String s = "The quick brown fox jumped over the lazy dog";
static char[] chA=new char[s.length()*2];
static int index=0;
static int cindex=0;

public static void main(String[] args){

System.out.println(recurse(s,s.length(),index/*,safe*/));

}

public static String recurse (String s, int len, int index){

chA[cindex]=s.charAt(index);
chA[cindex+1]='\$';
cindex+=2;
if(cindex==(s.length()*2)){return new String(chA);}
index+=1;
return recurse(s,0, index);

}

}
```