10 Replies - 639 Views - Last Post: 16 August 2017 - 02:13 PM Rate Topic: -----

#1 Dewey Banks  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#3 NormR  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 635
  • View blog
  • Posts: 4,827
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3417
  • View blog
  • Posts: 15,410
  • 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?
Was This Post Helpful? 0
  • +
  • -

#5 Dewey Banks  Icon User is offline

  • New D.I.C Head

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

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

Posted 12 August 2017 - 01:12 PM

View Postg00se, 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

Was This Post Helpful? 0
  • +
  • -

#6 NormR  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 635
  • View blog
  • Posts: 4,827
  • Joined: 25-December 13

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

Posted 12 August 2017 - 01:20 PM

Quote

add %20 between each character

Did you try it? What happened?

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

Was This Post Helpful? 0
  • +
  • -

#7 Dewey Banks  Icon User is offline

  • New D.I.C Head

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

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

Posted 12 August 2017 - 01:31 PM

View PostNormR, on 12 August 2017 - 01:20 PM, said:

Quote

add %20 between each character

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

Was This Post Helpful? 0
  • +
  • -

#8 Dewey Banks  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#9 NormR  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 635
  • View blog
  • Posts: 4,827
  • 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.
Was This Post Helpful? 0
  • +
  • -

#10 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3417
  • View blog
  • Posts: 15,410
  • 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
Was This Post Helpful? 0
  • +
  • -

#11 Arthur O Podd  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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);

 }

}

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1