Is this recursion a bad idea and does it make for clean code?

Question

This is a program I made to bounce the letter a across the screen. I made a few others, but this one I made with a recursive bounce() method. I know main() is a bit empty, but I intend to make an input menu that main refrences, so it seemed better to put the code in another method.

Is my code clean (probably far from it)? Easy to read? Am I overdoing the comments, or not specifing the code well enough?
Is it a bad idea using a recursive method for this as it has to keep memory for 80 recursions? It seemed like a good idea, because I was condensing so much more code into a smaller space.

/**
 * This code is designed for use with CMD with an 80
 * ASCII character width space.
 * It adds and subtracts a space to a string and out prints
 * the line.
 * It uses recursion to create one full Right-Left cycle,
 * then uses an infinite while loop to repeat.
 */

class Wave8 {

  static String spaces = "";            // Holds the spaces
  static boolean direction = true;      // True is right, false is left

  // Bouncing loop
  public static void bounce() {

    if (spaces.length() == (80 - 1)) {        // Width minus the string after lead
      System.out.print(spaces + "a");

      direction = false;                      // Change direction
    }
    else
      System.out.println(spaces + "a");

    if (direction) {          // If going right
      spaces += " ";
      bounce();               // Recursion
    }

    if (!direction) {         // If going left
      spaces = spaces.substring(1);

      if (spaces.isEmpty()) {
        direction = true;
        return;
      }
      else System.out.println(spaces + "a");       // Normal routine

    }
  }


  public static void main(String args[]) {

    while (true) {
      bounce();
    }
  }
}

Also, is there a way to test for efficiency? That would help greatly.

Answer 1

Before explaining why I think recursion might be a bad idea here, let me show you the solution I came up with.

class Wave8 {

  public static void bounce() {
    String spaces = "";
    for (int i=0; i<80; i++, spaces += " ")
    {
        System.out.println(spaces + "a");
    }
    for (int i=0; i<80; i++, spaces = spaces.substring(1))
    {
        System.out.println(spaces + "a");
    }
  }

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

The advantage of this solution against the recursive one :

• clarity : one can clearly see what was intended.

• termination : there is no doubt on the fact that this solution will eventually return

• no use of object members : if I call bounce() twice, I expect it to behave the same way twice.

• performance : I'd expect this solution to be much faster.

On the other hand, many functions are much better when written in a recursive way. This is the case when it's easy to see that we call the function on a "smaller" problem.

Answer 2

Recursion is fun as a mind-expanding exercise. However, excessive recursion is a bad idea in Java, because the language does not support tail recursion. Each time you call a function, a frame is added to the stack for bookkeeping. If the stack grows too large, you will get a StackOverflowError. You can get away with 80 levels, but deep recursion is frowned upon in Java. (In languages such as LISP, which do support tail recursion, recursion is very much a common and viable strategy.)

Usually, when you recurse, you call the function with parameters that vary in an interesting way. The function would test the parameters to see if it has reached a "base" case, and decides whether to recurse or return. In your code, you're mutating the state of the object, so there's no point to using recursion.

Here's an effective recursive solution:

public class Wave8 {
    public static void bounce() {
         bounce("", 79);
    }

    private static void bounce(String spaces, int remaining) {
        System.out.println(spaces + "a");
        if (remaining > 0) {
            bounce(spaces + " ", remaining - 1);
            if (!spaces.isEmpty()) {
                System.out.println(spaces + "a");
            }
        }
    }

    public static void main(String[] args) {
        // This still has to be iterative, because Java doesn't
        // support tail recursion, and therefore can't recurse
        // infinitely.
        while (true) {
            bounce();
        }
    }
}

See how short and sweet it is? In particular, notice the complete lack of instance and class variables, and, usually, of local variables too. That's what makes recursion an attractive strategy — all of the state is implicitly stored in the stack.