Рекурсия массива

Вот словами , как бы я это сделал:

Если осталось не более трех лампочек, довольно легко проверить, могут ли они быть переключился так, что это правильно.

Если лампочек больше трех, выполните следующие действия:

Убедитесь, что первая лампочка правильная. Если это так, продолжайте рекурсивно с подмассивом, начиная со второй лампочки.

Если первая лампочка не подходит, включите вторую лампочку (переключение первой лампы не сработает, потому что предыдущие лампы переключаются обратно). Теперь первая лампочка правильная. Продолжайте с подмассивом, начиная со второй лампочки.

Спасибо всем за помощь, вот что у меня получилось:

public static boolean disco(boolean[] init, boolean[] target)
{
    if (java.util.Arrays.equals(init, target)) {
        return true;
    } else {
        return disco(init, target, 0);
    }
}

private static boolean disco(boolean[] init, boolean[] target, int i)
{
    if (i > init.length-1) {
        return false;
    }

    disco(init, target, i+1);
    boolean t = false;

    if (init[i] != target[i]) {
        switchBulb(init, target, i);
    }

    if (java.util.Arrays.equals(init, target)) {
        t = true;
    }

    return t;
}

private static void switchBulb(boolean[] init, boolean[] target, int i)
{
    if ( (i > 1) && (init[i-1] != target[i-1]) && (init[i-2] != target[i-2]) ) {
        // If there's a series of 3 opposite-to-target bulbs, switch the middle one & from both sides
        init[i-1] = !init[i-1];
        init[i] = !init[i];
        init[i-2] = !init[i-2];
    } else if (i > 0 && i < init.length-1) {
        // There's only 1 bulb or 2 adjacent bulbs that are opposite of target.
        if (i == 1 && (init[0] != target[0]) ) {
            // First 2 bulbs are opposite of target's, so switch the 1st one.
            init[i-1] = !init[i-1];
            init[i] = !init[i];
        } else if ( (i == init.length-2) && (init[i+1] != target[i+1]) ) {
            init[i+1] = !init[i+1];
            init[i] = !init[i];
        } else {
            init[i] = !init[i];
            init[i-1] = !init[i-1];
            init[i+1] = !init[i+1];
        }
    } else {
        // First bulb or last bulb.
        init[i] = !init[i];
        if (i == 0) {
            init[i+1] = !init[i+1];
        } else {
            init[i-1] = !init[i-1];
        }
    }
}

Я чувствую, что мое использование рекурсии здесь минимально, могло бы быть намного чище, если бы рекурсия использовалась правильно. Any thoughts? Я говорю о функции switchBulb, ее можно заменить более сложной логикой рекурсии, или я ошибаюсь?

Например, если просто перебирать лампочки по одной и сравнивать с целевым массивом, то не обязательно получится правильно для ВСЕХ комбинаций лампочек (см. пример), так как же имитировать случайное переключение лампочек с помощью рекурсии? Или есть какая-то закономерность? Должна быть, если нет, то как она узнает, когда остановиться?

Кажется, я нашел решение, напишу позже, если кому-то интересно...

Подсказка: Пусть a1, a2, ..., ak, ..., an - входные данные, а b1, b2, ..., bk, ..., bn - желаемый выход.

Вы можете рекурсивно проверить левую и правую стороны, а затем объединить результат. Самое сложное - объединить результат.

Начнем с левой стороны.

1. Проверьте a1, a2, ..., ak, true на b1, b2, ..., bk, true.
   1. если true, то проверяем a1, a2, ..., ak на b1, b2, ..., bk.
      1. если true, то решение от a1, a2, ..., ak до b1, b2, ..., bk не может включать переключение k-го переключателя
      2. если false, то решение от a1, a2, ..., ak до b1, b2, ..., !bk должно включать переключение k-го переключателя
   2. если false, то тест a1, a2,...,ak до b1, b2,...,bk
      1. если true, то решение от a1,a2, ..., ak до b1, b2,..., bk должно включать переключение k-го переключателя
      2. если false, то решение от a1,a2,...,ak до b1, b2,..., bk не может включать переключение k-го переключателя

После двух тестов в левой части, вы можете провести аналогичные тесты в правой части. Вы сможете объединить значения тестов, так как будете знать, был ли переключен k-й переключатель или нет.