Как вернуть правильный логический параметр в рекурсивной функции?

Question

Я знаю, что общий шаблон для рекурсивных функций требует оператора возврата для каждого случая. Рассмотрим эту рекурсивную функцию, которая должна (но не может) возвращать true, если заданный список целых чисел может составлять 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++) {
        doArith(A,
                arith(temp,op,A.get(start)),
                start+1);
    }

    return false;
}

С помощью операторов печати в блоке базового варианта я точно знаю, что мой код правильно определяет, когда было сделано 24. Тем не менее, он не возвращает 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;
}

Но это все равно всегда возвращается false.

Как заставить эту функцию возвращать true в тот момент, когда она сталкивается с таким случаем?

Спасибо

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).