如何将这种递归Java方法转换为迭代方法？（CodeJam挑战）

Question

我正在尝试将这个solution适应Python的代码阻塞问题Dice Straight。不幸的是，它需要太深的递归才能在Python中正常工作（除非递归限制和堆栈大小都显著增加）。所以我试着把这个递归的method转换成迭代的：

/**
 * Attempt to recursively free a die by selecting a different die for the same value.
 * @return true if the die has been freed, false if no other die can be found.
 */
boolean freeByShuffling(Die die) {
    assert die.valueUsing != null;
    // First check if we can just use another dice for the previous value
    for (Die otherDie : die.valueUsing.dice) {
        if (otherDie.valueUsing == null) {
            otherDie.valueUsing = die.valueUsing;
            die.valueUsing = null;
            return true;
        }
    }
    // Nope, we must free a die recursively
    diceVisitedWhileShuffling.add(die);
    for (Die otherDie : die.valueUsing.dice) {
        if (diceVisitedWhileShuffling.contains(otherDie)) continue;
        if (freeByShuffling(otherDie)) {
            otherDie.valueUsing = die.valueUsing;
            die.valueUsing = null;
            return true;
        }
    }
    return false;
}

这是我的Python代码，虽然它解决了大多数测试用例，但并不十分有效：

def free_by_shuffling(self, die):
    assert die.current_value is not None

    stack = [(None, die)]
    found = False

    while stack:
        this_die, other_die = stack.pop()
        self.visited.add(other_die)

        if found:
            other_die.current_value = this_die.current_value
            this_die.current_value = None
            continue

        for next_die in other_die.current_value.dice:
            if next_die in self.visited:
                continue
            if next_die.current_value is None:
                found = True
                stack.append((other_die, next_die))
                break
        else:
            for next_die in other_die.current_value.dice:
                if next_die in self.visited:
                    continue
                stack.append((other_die, next_die))

    return found

如何将原始方法转换为使用迭代而不是递归？你知道吗

Answer 1

这个Python实现对“小”和“大”输入文件都适用：

def free_by_shuffling(self, die):
    assert die.current_value is not None

    stack = [die]
    found = False

    while stack:
        this_die = stack.pop()

        if found:
            if stack:
                this_die.current_value = stack[-1].current_value
                stack[-1].current_value = None
            continue

        for other_die in this_die.current_value.dice:
            if other_die.current_value is None:
                stack.extend((this_die, other_die))
                found = True
                break
        else:
            self.visited.add(this_die)

            for other_die in this_die.current_value.dice:
                if other_die not in self.visited:
                    stack.extend((this_die, other_die))
                    break
            else:
                if stack:
                    for other_die in stack[-1].current_value.dice:
                        if other_die not in self.visited:
                            stack.append(other_die)
                            break
    return found

欢迎提出意见和建议。你知道吗