Convert Iterative Loop to Recursive Method

2
votes

I got the exercise to write a function twice, once recursive, once iterative, which will produce the following output:

private static void printSequence(int n)

printSequence(3);

1
12
123
12
1

My iterative solution is the following:

for (int i = 1; i < 2 * n; i++) {
    for (int j = 1; j <= (i > n ? 2 * n - i : i); j++) {
        System.out.print(j);
    }
    System.out.println();
}

The iterative way is really simple, but I have no idea how to approach this as a recursive call.

Any tips on how to solve this problem?

EDIT: the method signature is fixed due to unit tests

2
javarecursioniteration
You can create two recursive methods, one for printing numbers in one line, second to recursively print first and last rows (depending on input). - Pshemo
Hint: You want to print the first line, call a subroutine to fill in the middle, then print the last line. The subroutine then becomes exactly the same as the main method. - Ordous

2 Answers

4
votes

Your code should look like this 

public static void main(String[] args) {
    recusiveFunction(1,10); // First parameter is the iteration number and 2 is total times.
}

private static void recusiveFunction(int iteration ,int total) {
    String str="";
    for(int i=1;i<=iteration;i++){ // this loops creates what it needs to print 1 or 12 or 123
        str+=i;
    }
    if(iteration<total/2){
        System.out.println(str);
        recusiveFunction(++iteration,total);
    }
    System.out.println(str);
}

Output:

1
12
123
1234
12345
1234
123
12
1

How this works is the we store the string in a variable that we want to print but we keep calling the function and increment the string is the iteration are less than half. then once it reaches half it start returning the stack trace so it gives us the return output in decreasing order.

Edit :

As said by pshemo modified the code a little bit to have absolutely no loops:

public static void main(String[] args) {
    recusiveFunction(1,10,"");
}

private static void recusiveFunction(int iteration ,int total, String str) {
    str+=iteration;
    if(iteration<total/2){
        System.out.println(str);
        recusiveFunction(++iteration,total,str);
    }
    System.out.println(str);
}

Output:

1
12
123
1234
12345
1234
123
12
1

Alternative way:

public class Main {
    private  static int iteration=1;
    private  static String str ="";

    public static void main(String[] args) {
        printSequence(10);
    }

    private static void printSequence(int total) {
        if(iteration<=total){
            str+=iteration;
            System.out.println(str);
            iteration++;
            printSequence(total);
        }
        if(2*total - iteration >0) {
            str = str.substring(0, 2 * total - iteration);
            iteration++;
            System.out.println(str);
        }
    }
}

Output:

1
12
123
1234
12345
123456
1234567
12345678
123456789
12345678910
123456789
12345678
1234567
123456
12345
1234
123
12
1
1
votes

Hint: Your main recursive method can look like

void recursiveMethod(int iter, int max){
    if iteration<max
        print 1..iter
        recursiveMethod(iter+1, max)
        print 1..iter
    else
        print 1..iter
}

You can write additional recursive method which will handle printing numbers in range 1..n

        print 1..iter
        recursiveMethod(iter+1, max)
        print 1..iter

should handle printing 

1
..
1

but will also invoke recursiveMethod(iter+1, max) which will fill .. part with

12
..
12

and so on, until case where iteration==max where we need to print only

123..max