Rekurze

Co je to rekurze?

Metoda, která volá sama na sebe se nazývá rekurzivní. Takže, když metoda volá sama na sebe, tomu se říká rekurze. Klíčovou složkou rekurzivní metody je příkaz, který provádí volání na sebe sama.

K čemu je rekurze dobrá?

Rekurze se dá jednoduše použít při počítání faktoriálu. Pokud nevíte co je to faktoriál, tak si to teď vysvětlíme. Faktoriál z čísla N je součin všech celých čísel mezi 1čkou a N. Faktoriál z čísla 5 je 1 * 2 * 3 * 4 * 5 = 120. Takže faktoriál z čísla 5 je 120.

Bez rekurze by jste následující příklad řešili asi cyklem. No podívejme se na to jak bych to bez rekurze řešil já a samozřejmě mnozí z vás.

hlavní třída Program.java

public class Program {
    public static void main(String args[]){
        // vytvořím nový objekt třídy Faktorial
        Faktorial f = new Faktorial();
        // vypíšu faktoriál z čísla 5
        System.out.println(f.faktorial(5));
    }
}

Třída Faktorial.java

public class Faktorial {
    // Vytvořím veřejnou metodu, která vrací Integer.
    public int faktorial(int n){
        // N je číslo, z kterého chceme dostat faktoriál.
        int i, vysledek = 1;
        // součin všech čísel mezi 1 a N
        for(i = 1; i <= n;i++)
            vysledek = vysledek * i;
        // vrátím faktoriál z čísla N
        return vysledek;
    }
}

Jak jste si asi všimli, veřejná metoda faktoriál ve třídě Faktorial nám vrátil součin všech čísel od 1 do 5 (tedy N). Teď se podíváme na stejný příklad akorát s rekurzí.

Hlavní třída Program.java, je stejná jako ta předchozí.

public class Program {

    public static void main(String args[]){
        Faktorial f = new Faktorial();
        System.out.println(f.faktorial(5));
    }
}

Třída Faktorial.java, v které už je použita rekurze.

public class Faktorial {

    public int faktorial(int n){
        int vysledek;
        if(n == 1)
            return 1;
        vysledek = faktorial(n-1) * n;
        return vysledek;
    }
}

Jak vidíme, metoda volá sama na sebe "vysledek = faktorial(n-1) * n;", tudíž můžeme s klidem říct, že je rekurzivní. Je o dost jednodušší, než kdyby jsme použili cyklus. Při zavolání metody faktorial s argumentem 1 vrátí metoda 1čku. V opačném případě vrátí součin faktorial(n-1) - n. Pro vyhodnocení tohoto výrazu, se zavolá metoda faktorial() s hodnotou n-1. Tento proces se opakuje, dokud se n nerovná 1 a volání metody se nezačnou vracet. Například při volání výpočtu faktoriálu z čísla 2 způsobí první volání metody faktorial() provedení druhého volání s argumentem 1. Toto volání vrátí hodnotu 1, která se následně vynásobí číslem 2. Odpověď je tedy 2.

Další ukázkoví příklad rekurze je Fibonacciho posloupnost. Pokud nevíte co to je -> http://cs.wikipedia.org/…_posloupnost .

Nicméně ukázka Fibonacciho posloupnosti. O(2ⁿ)

public class Program {

    public static void main(String args[]){
        Fibonacci fib = new Fibonacci();
        System.out.println(fib.fibonaci(5));
    }
}

Fibonacci.java

public class Fibonacci {

    public int fibonaci(int n)
    {
        if (n == 1) return 1;
        else return fibonaci(n-1) + fibonaci(n-2);
    }
}

Hodně z vás by mi teď řeklo "bože to je pomalý to je hrůza", tak bohužel ano. Je to opravdu pomalé. Každopádně má to jedno super řešení jak to O(2ⁿ) zoptimalozivat na O(n). Trochu už zabíhám do algoritmů já vím. Nemůžu si pomoct.

public class Fibonacci {
    private List<Integer> list = new ArrayList<Integer>();
    public int fibonaci(int n)
    {   list.add(n);
        if (n == 1) return 1;
        if(!list.contains(n-1)) return fibonaci(n - 1);
        if(!list.contains(n-2)) return fibonaci(n - 2);
        return 0;
    }
}

O mnoho lepší, že? Stačilo si vytvořit list a sypat do něj hodnoty co přijdou, aby se neopakovali a ověřovat jestli tam ještě nejsou. Tím se to pěkně zrychlí a z O(n²) máme hnedle O(n).