Infinite loop in recursion

Question

I'm putting together a code to output the following pattern:

000000000X
00000000XX
0000000XXX
000000XXXX
00000XXXXX
0000XXXXXX
000XXXXXXX
00XXXXXXXX
0XXXXXXXXX

(each line should be one after another. I'm not quite sure how to display the pattern on forums...sorry)

I'm supposed to use a recursive loop inside the code but I end up in an infinite loop and I really don't understand why..(It may be ok to assue that I've never used a recursive loop practically).This is my code:

class Recursion {
    //recursion should stop after 9 attempts
    static int stopindex = 9;

    public static void main(String[] args) {
        //a=number of "O"s and b=number of "X"s
        int a = 9;
        int b = 1;
        recursion(a, b);
    }
    public static void recursion(int a, int b) {

        //start of recursion at index 1
        int startindex = 1;

        //stop condition of recursion
        if (startindex == stopindex)
            return;

        //printing of pattern
        for (int i = a; i > 0; i--) {
            System.out.print("O");
        }
        for (int j = 0; j < b; j++) {
            System.out.print("X");
        }
        System.out.println();

        --a;
        ++b;
        ++startindex;
        recursion(a, b);
    }
}

Elliott Frisch · Accepted Answer · 2014-08-20 03:34:19Z

7

Your algorithm is slightly off, you shouldn't have the static variables and you shouldn't change a, and your first for loop condition - I think you wanted,

public static void recursion(int a, int b) {
  // stop condition of recursion
  if (a == b) return;

  // printing of pattern
  for (int i = a - b; i > 0; i--) {
    System.out.print("O");
  }
  for (int j = 0; j < b; j++) {
    System.out.print("X");
  }
  System.out.println();

  // --a;
  ++b; // <-- this could be done in the recursion call below,
  recursion(a, b);
  // recursion(a, ++b); // <-- like that.
}

The output is

OOOOOOOOX
OOOOOOOXX
OOOOOOXXX
OOOOOXXXX
OOOOXXXXX
OOOXXXXXX
OOXXXXXXX
OXXXXXXXX

answered Aug 20, 2014 at 3:34

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3889963 Over a year ago

Nice use of for loop...Never used it like that before. Thanks again.

alex · Accepted Answer · 2014-08-20 03:33:02Z

You are resetting the variable startindex at the start of recursion method, so if the recursion method is called and startindex is increased by one and then the method is called upon again the variable will be reset, due to int startindex = 1;.

class Recursion {
static int stopindex = 9;
int startindex = 1;
public static void main(String[] args) {
    //a=number of "O"s and b=number of "X"s
    int a = 9;
    int b = 1;
    recursion(a, b);
}
public static void recursion(int a, int b) {

    //start of recursion at index 1
    //int startindex = 1; - removed due to variable reset

    //stop condition of recursion
    if (startindex == stopindex)
        return;

    //printing of pattern
    for (int i = a; i > 0; i--) {
        System.out.print("O");
    }
    for (int j = 0; j < b; j++) {
        System.out.print("X");
    }
    System.out.println();

    --a;
    ++b;
    ++startindex;
    recursion(a, b);
}
}

Santanu Dey · Accepted Answer · 2014-08-20 03:36:15Z

Your problem is that your start index gets reset each time the function is called. Try this code

class Recursion {
//recursion should stop after 9 attempts
static int stopindex = 9;

public static void main(String[] args) {
    //a=number of "O"s and b=number of "X"s
    int a = 9;
    int b = 1;
    int startindex = 1;
    recursion(a, b, startindex);

}
public static void recursion(int a, int b, int startIndex) {

    //start of recursion at index 1


    //stop condition of recursion
    if (startIndex > stopindex)
        return;

    //printing of pattern
    for (int i = a; i > 0; i--) {
        System.out.print("O");
    }
    for (int j = 0; j < b; j++) {
        System.out.print("X");
    }
    System.out.println();

    --a;
    ++b;
    ++startIndex;
    recursion(a, b, startIndex);
}
}

Output

OOOOOOOOOX
OOOOOOOOXX
OOOOOOOXXX
OOOOOOXXXX
OOOOOXXXXX
OOOOXXXXXX
OOOXXXXXXX
OOXXXXXXXX
OXXXXXXXXX

Alexander Gessler · Accepted Answer · 2014-08-20 03:37:03Z

0

You don't need startindex at all - your parameter a is all you need to formulate the halting condition for the recursion. For every recursive invocation of recusion, a is one less and once a == 0 you break the recursion.

As is, you are resetting startindex to 1 every time so the breaking condition is always false.

public static void recursion(int a, int b) {
    if (a == 0) {
       return;
    }

    // Print here

    recursion(a - 1, b + 1);
}

edited Aug 20, 2014 at 3:37

answered Aug 20, 2014 at 3:30

Alexander Gessler

46.9k7 gold badges86 silver badges124 bronze badges

Collectives™ on Stack Overflow

Infinite loop in recursion

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related