17154

Method to return a fractal sequence (1 12 123 1234 …) as a string, but last sequence is printing twi

Question:

The point of this program is to return a "fractal sequence" up until some number, n. That sounds fancy, but all it means is that if, say, n = 4, then it would return: 1 1 2 1 2 3 1 2 3 4. (It just counts up to 1, then 2, then 3, then 4, and returns each step as it gets there.) To make it easier to see: 1 12 123 1234.

<ol><li>

The method is called "foo", and the main method <em>must print</em> it. So, the main method calls it by going System.out.print(foo(4)).

</li> <li>

The foo method must return a string.

</li> <li>

Loops may appear in the foo method, but the point of the exercise is to solve the problem <strong>recursively</strong>, and so the bulk of the work is supposed to feature a <strong>recursion</strong>. Or else, this would be a lot easier with some for loops!

public class test{ public static void main(String args[]){ System.out.print(foo(4)); } public static String foo(int n){ String s = ""; if(n == 1){ //Base step of the recursion s = 1 + " "; } else{ s = foo(n-1) + n + " "; //Recursive step of the recursion } System.out.print(s); return s; } } </li> </ol>

Right now, what the program will print is 1 1 2 1 2 3 1 2 3 4 <strong>1 2 3 4</strong>.

The problem is that it is printing out an extra set of 1 2 3 4 at the end. I realize the reason why it's doing that is because System.out.print(s) prints out everything I need, but then the extra System.out.print(foo(4)) in the main method is printing out the extra 1 2 3 4 at the end.

This could easily be solved if in the main method, I just took out System.out.print, and just wrote foo(4);. But, like rule (1) says, the main method must have the print. I'm <strong>not</strong> allowed to edit anything outside the foo method.

I have tried a bunch of different things (for about 7 hours or so now), but I don't seem to be "getting it". Can someone shed light on where I am going wrong?

Thank you sincerely!

Answer1:

This should work:

pulic class test { public static void main(String args[]) { System.out.print(foo(4)); } public static String foo(int n) { String s = ""; if(n == 0) { //do nothing } else { s = foo(n-1); System.out.print(s); s=s+n; } return s; } }

Answer2:

I first thought about an iterative solution to this.

//Iterative Solution public static String bar(final int n){ final StringBuilder builder = new StringBuilder(); for (int i = 1; i <= n ; i++) { for (int j = 1; j <= i ; j++) { builder.append(j); } builder.append(" "); } return builder.toString(); }

The fact that this relies on 2 nested loops suggests to me that it is not possible to produce a recursive solution using only a single method and no loops. So I've had to include a loop to build up the individual sections within the recursion.

//Recursive Solution (with some iteration too) public static String foo(final int n) { if( n == 1 ) { return 1 + " "; } String s = ""; for (int i = 1; i <= n; i++) { s += i; } return foo(n-1) + s + " "; }

Both of these produce the same output when called with 4, so my main method:

public static void main(final String args[]){ System.out.println(bar(4)); System.out.println(foo(4)); }

Produces this output:

<blockquote>

1 12 123 1234

1 12 123 1234

</blockquote>

Answer3:

Change the method to:

public static String foo(int n){ String s = ""; if( n <= 0 ) { //Base step of the recursion s = ""; } else { String foo = foo(n-1); s = foo + foo.substring(foo(n-2).length(), foo.length() -1) + n + " "; //Recursive step of the recursion } return s; }

[Edit]:

Explanation:

What we need here is an accumulator. However, just using foo(n-1) + n will just give us the sequence 12345. So we need to get the last part of the n-1 sequence to get the full 1 12 123 1234 ... I have not tested this code, maybe you need to use foo.substring(foo.length - n, foo.length), but i thought n-1 should be correct. This just retrieves the last sequence ( 123 from 112123 ).

I changed the boundaries because i forgot the space.

With space:

s = foo + foo.substring(foo.length()- n, foo.length() -1) + n + " ";

Without space:

s = foo + foo.substring(foo.length()- (n-1), foo.length()) + n;

[Edit 2]

Didn't work for values n > 10, the new version uses foo(n-2) to figure out the substring. Note that this changes the complexity class for the worse. A better version would either be iterative and use dynamic programming, or use Integer Lists instead of Strings.

Answer4:

Right now you are printing the result of the recursion as well as each step. As the result is "1 2 3 4" you get this doubled.

1 for `System.out.print(s);` on step 1 1 2 for `System.out.print(s);` on step 2 1 2 3 for `System.out.print(s);` on step 3 1 2 3 4 for `System.out.print(s);` on step 4 1 2 3 4 for `System.out.print(foo(4));`

so calling foo(4); will get the result you want

Recommend

  • Recursion in ASP.NET Core Razor views
  • Cassandra 2.1: Recursion by nesting UDT's
  • Retrieving values from a PHP Multi-dimensional Array
  • @tailrec why does this method not compile with 'contains a recursive call not in tail position&
  • Regex for Specific Tag
  • pandas computation in each group
  • Excel VBA How to populate a multi-dimensional (3d) array with values from multiple excel ranges?
  • How can we prepend rows to a react native list-view?
  • In matplotlib, how do you change the fontsize of a single figure?
  • Primefaces ManyCheckbox inside ui:repeat calls setter method only for last loop
  • jQuery: add elements until a particular height is reached
  • Spring: No transaction manager has been configured
  • SAVE attribute needed for Fortran variables when only the C_LOC address is returned to a C program?
  • accepts_nested_attributes_for practical form use for in Rails 3
  • Object and struct member access and address offset calculation
  • What's the purpose of QString?
  • Reduction and collapse clauses in OMP have some confusing points
  • How to write order and limit within cakephp joins array
  • Textfile Structure (tables)
  • Jackson Parser: ignore deserializing for type mismatch
  • How to Cache Real-time Data?
  • Record samples being played with OpenAL
  • Unity3D & Android: Difference between “UnityMain” and “main” threads?
  • Spring Data JPA custom method causing PropertyReferenceException
  • Projection media query: browser support and workarounds?
  • Possible to stop flickering java tooltip in heavyweight mode?
  • How to set my toolbar fixed while scrolling android
  • R: gsub and capture
  • AT Commands to Send SMS not working in Windows 8.1
  • Windows forms listbox.selecteditem displaying “System.Data.DataRowView” instead of actual value
  • How get height of the a view with gone visibility and height defined as wrap_content in xml?
  • FormattedException instead of throw new Exception(string.Format(…)) in .NET
  • apache spark aggregate function using min value
  • unknown Exception android
  • EntityFramework adding new object to nested object collection
  • Checking variable from a different class in C#
  • Sorting a 2D array using the second column C++
  • failed to connect to specific WiFi in android programmatically
  • java string with new operator and a literal
  • How can I use threading to 'tick' a timer to be accessed by other threads?