Rekurze

Java Základní konstrukce 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(2n)

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é. :D Každopádně má to jedno super řešení jak to O(2n) 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(n2) máme hnedle O(n).


 

Stáhnout

Staženo 349x (31.31 kB)
Aplikace je včetně zdrojových kódů v jazyce java

 

  Aktivity (1)

Článek pro vás napsal Зайчик
Avatar
Коммунизм для нашего будущего!

Jak se ti líbí článek?
Celkem (6 hlasů) :
3.53.53.53.5 3.5


 



 

 

Komentáře
Zobrazit starší komentáře (69)

Avatar
Luboš Běhounek (Satik):

Nevím jak ty, ale čím víc tříd v projektu (pokud jich je opravdu hodně), tím více se začínám ztrácet a hůře si to dokážu celé představit.

Odpovědět 12.4.2013 10:44
:)
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

Proto jsou v Javě balíky. Slouží k tomu, aby sis aplikaci logicky rozdělil. Plošná struktura se dá použít jen na menší projekty.

Odpovědět 12.4.2013 12:55
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Hartrik
Redaktor
Avatar
Hartrik:

Docela by mě zajímalo, jak se něco takového může stát u tak velkého projektu, na kterém určitě pracoval celý tým programátorů.

 
Odpovědět  +1 12.4.2013 20:13
Avatar
Kit
Redaktor
Avatar
Odpovídá na Hartrik
Kit:

To netuším. Přepisovat jim to nebudu, ale určitě bych ten kód zkrátil asi na třetinu. Je na tom patrné, jak se neustále nabalují nové vlastnosti bez revize těch stávajících.

Odpovědět 13.4.2013 9:53
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Hartrik
David Čápka:

Jednoduše, vznikl v době, kdy PHP nebylo objektové. Teď se to nikomu přepisovat nechce.

Odpovědět  +3 13.4.2013 9:58
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na Kit
Luboš Běhounek (Satik):

Téměř každý větší projekt vzniká nabalováním jako sněhová koule. A na revize nejsou téměř nikde finance ani čas.

Odpovědět 13.4.2013 10:19
:)
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

Pokud je dobrý návrh základu, tak k tomu ani nemusí dojít. Dobrou prevencí je TDD, refaktorovat pak můžeš kdykoli.

Odpovědět 13.4.2013 10:24
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Kit
Luboš Běhounek (Satik):

S tím návrhem je trochu potíž, protože téměř každý větší projekt se vyvíjí postupně a nikdy nevíš, co za požadavky ti přijde.

Odpovědět 13.4.2013 10:39
:)
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

Právě proto je dobré používat TDD, i když na začátku to připadá zdržující.

Odpovědět 13.4.2013 10:43
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Frunta
Redaktor
Avatar
Frunta:

Myslím si, že by bylo dobré se v článku zmínit i o dalších využitích rekurze. Mě bylo učeno například vyplňování určité části mapy (mapou mám na mysli int ahoj[50][50]).

Editováno 16.4.2013 19:47
 
Odpovědět 16.4.2013 19:46
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 79. Zobrazit vše