Method to return a fractal sequence (1 12 123 1234

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.

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

2. The foo method must return a string.

3. Loops may appear in the foo method, but the point of the exercise is to solve the problem recursively, and so the bulk of the work is supposed to feature a recursion. 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;
   
     }
   }
   

Right now, what the program will print is 1 1 2 1 2 3 1 2 3 4 1 2 3 4.

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 not 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!

Answer 1

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

Answer 2

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.

Answer 3

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;
    }
}

Answer 4

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:

1 12 123 1234

1 12 123 1234