如何从 drawSquare 方法中删除递归并获得完全相同的结果？

Question

我需要从 drawSquare 方法中删除递归。从该方法中删除递归后，我还有很多事情要做，但其余的我可以自己解决。我真的需要一个工作解决方案，它可以在不递归的情况下完成完全相同的事情，我会找出其余的。

这是我制作正方形的方法 class:

import java.awt.Color;

public class Square {
    final int BLACK = Color.BLACK.getRGB();
    final int WHITE = Color.WHITE.getRGB();
    protected int center_x;
    protected int center_y;
    protected int side;
    protected int color;
    protected Square parentSquare;

    public Square(){
        this.center_x = 0;
        this.center_y = 0;
        this.side = 0;
        this.color = WHITE;
        this.parentSquare = null;
    }
    public Square(int center_x,int center_y,int side,int color){
        this.center_x = center_x;
        this.center_y = center_y;
        this.side = side;
        this.color = color;
        this.parentSquare = null;
    }
    public Square(int center_x,int center_y,int side,int color,Square parentSquare){
        this.center_x = center_x;
        this.center_y = center_y;
        this.side = side;
        this.color = color;
        this.parentSquare = parentSquare;
    }
    public void setX(int center_x){
        this.center_x = center_x;
    }
    public int getX(){
        return center_x;
    }
    public void setY(int center_y){
        this.center_x = center_y;
    }
    public int getY(){
        return center_y;
    }
    public void setSide(int side){
        this.side = side;
    }
    public int getSide(){
        return side;
    }
    public void setColor(int color){
        this.color = color;
    }
    public int getColor(){
        return color;
    }
    public void setParent(Square parentSquare){
        this.parentSquare = parentSquare;
    }
    public Square getParent(){
        return parentSquare;
    }
}

这是原始的 Tsquare.java，它产生一个正方形的分形，从每个正方形的 4 个角分支直到边 = 0：（完整的 TSquare.java class 修改为使用 Square 对象）

import java.awt.image.*;
import java.awt.Color;
import java.io.*;
import javax.imageio.*;
import java.util.*;
public class TSquare {
    static final int SIDE = 1000; // image is SIDE X SIDE
    static BufferedImage image = new BufferedImage(SIDE, SIDE, BufferedImage.TYPE_INT_RGB);
    static final int WHITE = Color.WHITE.getRGB();
    static final int BLACK = Color.BLACK.getRGB();
    static Scanner kbd = new Scanner(System.in);

    public static void main(String[] args) throws IOException{
        String fileOut = "helloSquares.png";
        System.out.print("Enter (x,y) coordinates with a space between: ");
        int x = kbd.nextInt();
        int y = kbd.nextInt();
        System.out.println(x+","+y);//TESTLINE TESTLINE TESTLINE TESTLINE
        // make image black
        for (int i = 0; i < SIDE; i++) {
            for (int j = 0; j < SIDE; j++) {
                image.setRGB(i, j, BLACK);
            }
        }
        Square square = new Square(SIDE/2,SIDE/2,SIDE/2,WHITE);
        drawSquare(square);



        // save image
        File outputfile = new File(fileOut);
        ImageIO.write(image, "jpg", outputfile);
    }

    private static void drawSquare(Square square){ // center of square is x,y length of side is s
        if (square.side <= 0){ // base case
            return;
        }else{
            // determine corners
            int left = square.center_x - (square.side/2);
            int top = square.center_y - (square.side/2);
            int right = square.center_x + (square.side/2);
            int bottom = square.center_y + (square.side/2);
            int newColor =square.color-100000;
            Square newSquareA = new Square(left,top,square.side/2,newColor);
            Square newSquareB = new Square(left,bottom,square.side/2,newColor);
            Square newSquareC = new Square(right,top,square.side/2,newColor);
            Square newSquareD = new Square(right,bottom,square.side/2,newColor);
            for (int i = left; i < right; i++){
                for (int j = top; j < bottom; j++){
                    image.setRGB(i, j, square.color);
                }
            }
            // recursively paint squares at the corners
            drawSquare(newSquareA);
            drawSquare(newSquareB);
            drawSquare(newSquareC);
            drawSquare(newSquareD);
        }

    }

}

我希望重现此代码的确切操作，只是减去递归，但我尝试的一切似乎都不起作用。我什至无法在原始黑色上方显示一个白色方块 canvas。

Answer 1

这是一个使用 ArrrayDeque (https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html) 的实现。

值得将 ArrayDeque 与其他一些 Java 类型进行比较：

a) Stack是一个接口，api页面(https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html)说

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

b) 我最初使用熟悉的 ArrayList 编写此代码，使用 Square square = squares.remove(0); 而不是 pop。我很惊讶这个 ArrayDeque 实现看起来比 ArrayList 快多少（并不是说我有运行任何正式的基准测试）

private static void drawSquare(Square startSquare){

    Deque<Square> squares = new ArrayDeque<Square>(400000);
    squares.push(startSquare);

    while (!squares.isEmpty()) {
        Square square = squares.pop();

        System.out.println(square);
        // center of square is x,y length of side is s
        if (square.side > 0){ // base case
            // determine corners
            int left = square.center_x - (square.side/2);
            int top = square.center_y - (square.side/2);
            int right = square.center_x + (square.side/2);
            int bottom = square.center_y + (square.side/2);
            int newColor =square.color-100000;
            addSquare(squares, left,top,square.side/2,newColor);
            addSquare(squares, left,bottom,square.side/2,newColor);
            addSquare(squares, right,top,square.side/2,newColor);
            addSquare(squares, right,bottom,square.side/2,newColor);

        }
    }
}
private static void addSquare(Deque<Square> squares, int x, int y, int side, int color) {
    // STRONGLY recommend having this "if" statement !
    // if (side > 0) {
           squares.push(new Square(x, y, side, color));
    // }
}

正如我在评论中指出的那样，不创建大小为 0 的正方形而不是创建它们并在轮到它们时简单地忽略它们是非常值得的。这对于基于递归的操作也是如此 - 但对于这些基于非递归的操作尤其如此，因为大量的方块确实会占用内存和处理时间。

Answer 2

如果我们想要在不影响速度的情况下提高可读性，我建议首先对 Square:

添加一些内容

public int half() {
    return side/2;
}
public int left() {
    return center_x - half();
}
public int top() {
    return center_y - half();
}
public int right() {
    return center_x + half();
}
public int bottom() {
    return center_y + half();
}

public void draw(BufferedImage image) {

    int left = left();
    int top = top();
    int right = right();
    int bottom = bottom();

    for (int i = left; i < right; i++){
        for (int j = top; j < bottom; j++){
            image.setRGB(i, j, color);
        }
    }
} //End Square

同时将 I/O 移出以启用单元测试。

package com.Whosebug.candied_orange;
import java.awt.image.*;
import java.awt.Color;
import java.io.*;
import javax.imageio.*;
import java.util.*;
public class FractalSquareIterative {

    public static void main(String[] args) throws IOException{

        final int SIDE = 1000; // image is SIDE X SIDE        
        BufferedImage image = new BufferedImage(SIDE,SIDE,BufferedImage.TYPE_INT_RGB);

        drawImage(SIDE, image);
        saveImage(image);
    }

    //Removed IO to enable unit testing
    protected static void drawImage(final int SIDE, BufferedImage image) {
        final int BLACK = Color.BLACK.getRGB();
        final int WHITE = Color.WHITE.getRGB();
        final int HALF = SIDE / 2;

        //Draw background on whole image
        new Square(HALF, HALF, SIDE, BLACK).draw(image);

        //Draw foreground starting with centered half sized square
        Square square = new Square(HALF, HALF, HALF, WHITE);
        drawFractal(square, image);
    }

现在 Square 正在处理所有正方形的东西，分形代码看起来更容易一些。

    private static void drawFractal(Square square, BufferedImage image){

        Queue<Square> squares = new LinkedList<>();
        squares.add(square);

        while (squares.size() > 0) {

            //Consume
            square = squares.remove();

            //Produce
            int half = square.half();
            if (half > 2) {

                int left = square.left();
                int top = square.top();
                int right = square.right();
                int bottom = square.bottom();
                int newColor = square.color - 100000;                

                squares.add(new Square(left, top, half, newColor));
                squares.add(new Square(left, bottom, half, newColor));
                squares.add(new Square(right, top, half, newColor));
                squares.add(new Square(right, bottom, half, newColor));
            }
            square.draw(image);
        }
    }


    protected static void saveImage(BufferedImage image) throws IOException {
        String fileOut = "helloSquares.png";        
        File outputfile = new File(fileOut);
        ImageIO.write(image, "jpg", outputfile);
    }
} //End FractalSquareIterative

可靠地比递归版本快，但在这个大小下并不显着。

如果您想看一下我的单元测试，您会发现它们 here。

如何从 drawSquare 方法中删除递归并获得完全相同的结果？

How do I remove the recursion from the drawSquare method and get the exact same result?

java

recursion

computer-science

square

coordinates