java - 在java中使用循环将递归方法转换为非递归方法

Question

所以我目前正在制作一个游戏，其中的指令是使用存储在标记索引(在本例中为圆圈)处的整数在数组中向左或向右移动，直到我们可以将圆圈移至数组的最后一个索引.数组的最后一个整数始终为 0。

例如，

[4] 1 2 3 1 0，这里我们从圆圈 0(索引)开始

我们向右移动4，4 1 2 3 [1] 0

然后向右 1 次，4 1 2 3 1 [0]。游戏到此结束，我们赢了。

我的递归方法代码如下:

public static boolean rightWing (int circle, int[] game, List<Integer> checkerList){

int last = game.length-1;

if (circle == last){ // base case for recursion
    return true;
}

if (circle < 0){ // if we go out of bounds on the left
    return false;
}

if (circle > last){ // if we go out of bounds on the right
    return false;
}

if (checkerList.contains(circle)){ // check for the impossible case 
    return false;
}

checkerList.add(circle); // adds the circle value for the last check to checkerList so we can check for the impossible case

int moveRight = circle + game[circle]; // these two integers help the game move according to the value of the int at circle
int moveLeft = circle - game[circle];

return rightWing( moveRight, game, checkerList) || rightWing(moveLeft, game,checkerList);
}

这很好用，但唯一的问题是它是递归的而且很慢。我正在尝试使用循环和堆栈/队列重新设计它以使其更有效率，但在写完这篇文章后我被卡住了(伪):

   Boolean rightWing (int circle, List<int> game, List<int> checkerList)

Int lastPlace = game.size() - 1

For int i <- 0 to game.size() - 1 do

    If i equals lastPlace then // returns true when i is at the last position of the game
        Return true

任何关于如何前进的意见都将不胜感激!

Answer 1

最重要的一点:在针对运行缓慢问题调试应用时，您应该先收集一些性能数据，以确定您的应用将大部分时间花在了哪些地方。否则固定性能效率低下。您可以使用与 jdk 捆绑在一起的 jvisualvm。

数据结构统治性能世界

它可能变慢的一个原因是:

if (checkerList.contains(circle)){ // check for the impossible case 
    return false;
}

列表中的项目越多，它变得越慢。对于 contains 方法，List 具有线性复杂度。如果您使用 HashSet，则可以使它恒定复杂度。例如。如果您有包含 100 个元素的列表，使用 List 这部分的速度将比使用 HashSet 慢 100 倍左右。

另一件可能需要一些时间的事情是装箱/拆箱:每次将元素放入列表时，int 都会被包装到新的 Integer 对象中 - 这是称为拳击。您可能希望使用 IntSet 来避免装箱/拆箱并节省 GC 时间。

转换为迭代形式

我不希望这会影响您的申请速度，但只是为了回答的完整性。

将递归应用程序转换为迭代形式非常简单:在每次调用您的(或其他函数)时，隐藏的每个方法参数都存储在一个隐藏的堆栈中。在转换期间，您只需创建自己的堆栈并手动管理它

public static boolean rightWingRecursive(int circle, int[] game) {
    Set<Integer> checkerList = new HashSet<Integer>();
    Deque<Integer> statesToExplore = new LinkedList<>();
    
    int last = game.length - 1;
    
    statesToExplore.push(circle);
    
    while (!statesToExplore.isEmpty()) {
        int circleState = statesToExplore.pop();
        
        if (circleState == last) { // base case for recursion
            return true;
        }

        if (circleState < 0) { // if we go out of bounds on the left
            continue;
        }
        
        if (circleState > last) { // if we go out of bounds on the right
            continue;
        }
        
        if (checkerList.contains(circle)) { // check for the impossible case
            continue;
        }
        
        checkerList.add(circle); // adds the circle value for the last check to
        // checkerList so we can check for the
        // impossible case
        int moveRight = circle + game[circle]; // these two integers help the
        // game move according to the
        // value of the int at circle
        int moveLeft = circle - game[circle];
        statesToExplore.push(moveRight);
        statesToExplore.push(moveLeft);
    }

    return false;
}