CODEWITHSUNDEEP
javarecursion
Pat K
Pat K

Reputation: 321

Java: Recursive method accepts integer 'n' and prints 'n' characters

Homework: Looking for better strategy, or approach rather than complete code.

I am absolutely befuddled when trying to identify the recursive case for this problem. I have to write a method that accepts an integer parameter 'n' and then prints out a total of 'n' characters. The middle character should always be a '' or '*' depending on whether the original integer is odd or even. Here is what a couple of different method calls and output should look like:

writeChars(1) -> *
writeChars(2) -> **
writeChars(3) -> <*>
writeChars(4) -> <**>
writeChars(5) -> <<*>>
writeChars(6) -> <<**>>
writeChars(7) -> <<<*>>>
writeChars(8) -> <<<**>>>

How do I even go about trying to identify the recursive case?

Upvotes: 0

Views: 2077

Answers (5)

Bahman.A
Bahman.A

Reputation: 1296

I just assume two base cases, one for when n is even and one for when n is odd.

Now in the recursive call I pass n - 2; in the case of odd n, it ends up as 1 and for even n, it ends up as 2.

public static void writeChars(int n) {
    if(n < 1) 
        throw new IllegalArgumentException();
        
    if(n == 1)          //odd base case
        System.out.print("*");

    else if(n == 2)     //even base case
        System.out.print("**");
        
    else {              //recursive case
        System.out.print("<");
        writeChars(n - 2);
        System.out.print(">");
    }
}

Upvotes: 0

imdahmd
imdahmd

Reputation: 777

The way i thought about recursion is to pass two states (pos, string:s) that change over each recursive call and three states (n, mid1, mid2) that help in making decision on how to achieve the next state.

    public static void main(String... arg) {
        int n = 10, mid1, mid2;
        if (n % 2 == 0) {
            mid1 = n / 2;
            mid2 = n / 2 + 1;
        } else {
            mid1 = mid2 = n / 2 + 1;
        }

        System.out.println(recursion(1, n, mid1, mid2, ""));
    }

    private static String recursion(int pos, final int n, final int mid1, final int mid2, String s) {
        if (pos > n)
            return s;
        else if (pos == mid1 || pos == mid2)
            return recursion(pos + 1, n, mid1, mid2, s + "*");
        else if (pos < mid1)
            return recursion(pos + 1, n, mid1, mid2, s + "<");
        else
            return recursion(pos + 1, n, mid1, mid2, s + ">");
    }

Upvotes: 0

Arun P Johny
Arun P Johny

Reputation: 388416

I'll probably devide the problem into 3 parts 1. Print < 2. Print * 3. Print >

Base on this we can create a recursive solution to print each of the components. The number of < and > is based on a formula i % 2 == 1 ? i / 2 : (i - 2) / 2, then we can write a function to print them recursively then another one to print the *s.

public class SO15049082 {

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            print(i);
        }
    }

    private static void print(int i) {
        if (i > 0) {
            System.out.print("writeChars(" + i + ") --> ");
            int c = i % 2 == 1 ? i / 2 : (i - 2) / 2;
            printleft(c);
            printstar(c % 2);
            printright(c);
        }
        System.out.println();
    }

    private static void printright(int i) {
        if (i > 0) {
            System.out.print(">");
            printright(i - 1);
        }
    }

    private static void printstar(int i) {
        if (i == 1) {
            System.out.print("*");
        } else {
            System.out.print("**");
        }
    }

    private static void printleft(int i) {
        if (i > 0) {
            System.out.print("<");
            printleft(i - 1);
        }
    }

}

Upvotes: 0

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

To identify recursion, first think about how to solve the problem for a given value of n assuming you have a method that solves it for smaller cases. How does the solution for size n relate to the solution for size n-1?

After doing that, you will find one or more small cases that you cannot solve that way. Those are your base cases.

Finally, write a method that directly does each base case. For n larger than the base case, it calls itself for n-1, and then modifies that result to get the solution for size n.

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234847

You have two base cases: n == 1 and n == 2. Beyond that, the recursion rule is to emit a "<", recurse with n-2 (to account for the two characters you are going to emit at this level), then emit a ">".

Upvotes: 2

Related Questions