Rekurencja i backtracking w Javie z przykładami

Każda metoda rekurencyjna ma dwie części:

• Warunek stopu (przypadek bazowy) jest tak mały, że wynik jest od razu znany: liczba z jedną cyfrą, tekst z co najwyżej jednym znakiem, pusta tablica.
• Przypadek rekurencyjny sprowadza problem do mniejszej wersji tego samego problemu i w tym celu wywołuje samą metodę.

Warunek stopu zawsze sprawdzasz najpierw. W tablicach problem maleje, bo indeks przesuwa się dalej (index + 1), w tekstach przez substring(1), w liczbach przez n - 1 albo n / 10.

1public class Main {2    public static int countDigits(int n) {3        if (n < 10) {4            return 1;5        }6        return 1 + countDigits(n / 10);7    }8
9    public static String reverse(String s) {10        if (s.length() <= 1) {11            return s;12        }13        return reverse(s.substring(1)) + s.charAt(0);14    }15
16    public static void main(String[] args) {17        System.out.println(countDigits(7));18        System.out.println(countDigits(2026));19        System.out.println(reverse("stack"));20    }21}

Każde wywołanie metody dostaje własny obszar na stosie wywołań (call stack), czyli stosie z własnymi parametrami i zmiennymi lokalnymi dla każdego wywołania. Gdy factorial(4) wywołuje samą siebie, na końcu leżą jedno na drugim cztery wywołania, każde z własnym n. Dopiero gdy najwyższe się skończy, to pod nim działa dalej.

Wynika z tego: co stoi przed wywołaniem rekurencyjnym, wykonuje się w kolejności wywołań, a co stoi po nim, w odwrotnej kolejności. Wcięcia w przykładzie pokazują, jak głęboki jest w danej chwili stos.

1public class Main {2    public static int factorial(int n, String indent) {3        System.out.println(indent + "factorial(" + n + ") called");4        int result;5        if (n <= 1) {6            result = 1;7        } else {8            result = n * factorial(n - 1, indent + "  ");9        }10        System.out.println(indent + "factorial(" + n + ") returns " + result);11        return result;12    }13
14    public static void main(String[] args) {15        factorial(4, "");16    }17}

Stos ma ograniczony rozmiar. Kilka tysięcy wywołań jedno na drugim to nie problem, miliony już tak: wtedy Java przerywa działanie z StackOverflowError.

Wszystko, co potrafi pętla, potrafi też rekurencja, i odwrotnie. Obie sumy w przykładzie potrzebują O(n) kroków. Wersja rekurencyjna potrzebuje jednak dodatkowo O(n) miejsca na stosie, a pętla tylko jednej zmiennej.

Praktyczna zasada:

• Pętla, gdy po prostu przechodzisz tablicę albo listę od początku do końca.
• Rekurencja, gdy problem w naturalny sposób rozkłada się na podproblemy tego samego rodzaju: wieże Hanoi, drzewa, quicksort i sortowanie przez scalanie oraz wszystkie zadania, w których sprawdza się kolejne możliwości.

1public class Main {2    public static int sumRecursive(int[] numbers, int index) {3        if (index == numbers.length) {4            return 0;5        }6        return numbers[index] + sumRecursive(numbers, index + 1);7    }8
9    public static int sumLoop(int[] numbers) {10        int total = 0;11        for (int number : numbers) {12            total += number;13        }14        return total;15    }16
17    public static void main(String[] args) {18        int[] numbers = {4, 8, 15, 16, 23, 42};19        System.out.println(sumRecursive(numbers, 0));20        System.out.println(sumLoop(numbers));21    }22}

Backtracking buduje rozwiązanie krok po kroku. W każdym miejscu jest kilka możliwości. Dla każdej z nich obowiązuje ten sam schemat:

1. Wybierz: ustal jedną możliwość, np. dopisz literę i oznacz ją jako użytą.
2. Zbadaj: rekurencyjnie rozwiąż następny krok.
3. Cofnij: odwróć wybór, żeby następna możliwość startowała z czystego stanu.

Gdy rozwiązanie jest kompletne (wszystkie litery ułożone, wyjście osiągnięte), zostaje wypisane, policzone albo zapisane. Jeśli częściowe rozwiązanie przestaje pasować (hetman zagrożony, ściana na drodze), od razu porzuca się tę gałąź. Właśnie dlatego backtracking jest szybszy niż ślepe sprawdzanie wszystkich kombinacji.

1public class Main {2    static int found = 0;3
4    public static void permute(char[] letters, boolean[] used, StringBuilder current) {5        if (current.length() == letters.length) {6            System.out.println(current);7            found++;8            return;9        }10        for (int i = 0; i < letters.length; i++) {11            if (used[i]) {12                continue;13            }14            used[i] = true;                          // choose15            current.append(letters[i]);16            permute(letters, used, current);         // explore17            current.deleteCharAt(current.length() - 1);18            used[i] = false;                         // undo19        }20    }21
22    public static void main(String[] args) {23        char[] letters = {'a', 'b', 'c'};24        permute(letters, new boolean[letters.length], new StringBuilder());25        System.out.println(found + " permutations");26    }27}

Rozwiązania rekurencyjne, które w każdym wywołaniu wywołują same siebie dwa razy, szybko rosną. Wieże Hanoi potrzebują dla n krążków 2ⁿ − 1 ruchów, czyli O(2ⁿ). Każdy dodatkowy krążek podwaja pracę.

Tak samo jest z backtrackingiem: istnieje 2ⁿ podzbiorów i n! ustawień n elementów. Dla n = 20 to ponad milion podzbiorów i ponad 2 tryliony ustawień. Takie algorytmy nadają się tylko dla małych n. Porzucanie gałęzi, gdy tylko przestaje pasować, bardzo pomaga, ale często nie zmienia rzędu wielkości w najgorszym przypadku.

1public class Main {2    static long moves = 0;3
4    public static void move(int n, char from, char to, char via) {5        if (n == 0) {6            return;7        }8        move(n - 1, from, via, to);9        moves++;10        move(n - 1, via, to, from);11    }12
13    public static void main(String[] args) {14        for (int n = 1; n <= 20; n += 4) {15            moves = 0;16            move(n, 'A', 'C', 'B');17            System.out.println(n + " disks: " + moves + " moves");18        }19    }20}