如何 return 更正递归函数中的布尔值？

Question

我知道递归函数的通用模板要求每个案例都有一个 return 语句。考虑这个递归函数，如果给定的整数列表可以通过算术运算符 (*、/、+、-).

static boolean doArith(List<Double> A, double temp, int start) {
    // base case
    if (start == A.size()) return temp == 24;

    // recursive calls
    for (int op = 0; op < 4; op++) {
        doArith(A,
                arith(temp,op,A.get(start)),
                start+1);
    }

    return false;
}

通过基本案例块中的打印语句，我确信我的代码正确识别了 24 的生成时间。但是，当调用堆栈解析时，它无法 return true。

我尝试过重构代码，甚至将 for 循环硬编码为 4 个单独的调用，但不出所料，这没有用。

(编辑： 回应@Caramiriel 的评论) 我尝试将函数重写为：

static boolean doArith(List<Double> A, double temp, int start) {
    // base case
    if (start == A.size()) return temp == 24;

    boolean b = false;
    // recursive calls
    for (int op = 0; op < 4; op++) {
        b = doArith(A,
                arith(temp,op,A.get(start)),
                start+1);
    }
    return b;
}

但这仍然 return 总是 false。

遇到这种情况，如何让returntrue这个函数呢？

谢谢

Answer 1

如果导致结果为24的操作，你知道答案是正确的，需要跳出循环：

static boolean doArith(List<Double> A, double temp, int start) {
    // base case
    if (start == A.size()) return temp == 24;

    // recursive calls
    for (int op = 0; op < 4; op++) {
        boolean b = doArith(A,
                arith(temp,op,A.get(start)),
                start+1);

        if(b) {
            return true;
        }
    }

    return false;
}

以下代码：

boolean b = false;
// recursive calls
for (int op = 0; op < 4; op++) {
    b = doArith(A,
            arith(temp,op,A.get(start)),
            start+1);
}

只检查最后一个案例 (op = 3)。

如何 return 更正递归函数中的布尔值？

How to return correct boolean in recursive function?

recursion

callstack

boolean

return

terminate