Rekurze v Javě (i jinde)

Artii

Rekurze v Javě (i jinde)
« kdy: 19. 11. 2020, 08:39:08 »
Ahoj, měl bych takový menší dotázek ohledně rekurze v javě (ale i obecně):

Kód: [Vybrat]
public void metoda1 (x,y){
if(podminka){
                doSomething(x,y);
metoda1(x+1,y);
metoda1(x-1,y);
metoda1(x,y+1);
metoda1(x,y-1);
}
}

Toto bych (kvůli mé ubohé znalosti) očekával že vždy pokud
Kód: [Vybrat]
podminka==true tak se spustí pouze první řádek v if bloku, tedy
Kód: [Vybrat]
metoda1(x+1,y);
Pokud se během vykonávání
Kód: [Vybrat]
doSomenthig(x,y) změní podmínka v if na false tak se přeskočí celý if blok (to je jasné), ale pak skočí rovnou na metodu na druhém řádku
Kód: [Vybrat]
metoda1(x-1,y);
Myslel jsem si že takový kód je špatný, že se vždy spustí jen metoda na prvním řádku. Ono to ale funguje v podstatě přesně tak jak bych chtěl.  Takto se to chová vždy a všude? nebo mi něco uniká? díky za radu nebo spíš poučení :).


Re:Rekurze v Javě (i jinde)
« Odpověď #1 kdy: 19. 11. 2020, 09:15:03 »
1. Když píšeš že "to ale funguje v podstatě přesně tak jak bych chtěl. ", tak se mi zdá, že už máš nějaký funkční kód. V takovém případě je asi lepší postnout sem ten, ať neřešíme něco co je třeba jinak.

2. Když už máš funkční kód, doporučuju ti prokrokovat si ho v debuggeru, to ti v tom udělá jasno.

Jinak dejme tomu, že se ti zavolá doSomething(x,y); metoda1(x+1,y). Rekurzivní volání metoda1 si uvnitř něco dělá, představ si že je to blackbox a rekurzi úplně odmysli. Až tenhle blackbox skončí a vrátí se, prostě se spustí další řádek, tedy metoda1(x-1,y); a chová se úplně stejně, rekurze nerekurze. Až (jestli) někdy skončí, zavolá se další řádek...
« Poslední změna: 19. 11. 2020, 09:19:01 od registrovany_ava »

Re:Rekurze v Javě (i jinde)
« Odpověď #2 kdy: 19. 11. 2020, 09:17:07 »
1. Když píšeš že "to ale funguje v podstatě přesně tak jak bych chtěl. ", tak se mi zdá, že už máš nějaký funkční kód. V takovém případě je asi lepší postnout sem ten, ať neřešíme něco co je třeba jinak.

2. Když už máš funkční kód, doporučuju ti prokrokovat si ho v debuggeru, to ti v tom udělá jasno.

Jinak v postnutém kódu se skutečně vždy spustí buď pouze doSomething(x,y); metoda1(x+1,y), nebo vůbec nic.

Nesmysl, na stejne urovni rekurze se spusti se vsechny metody, nebo zadna.

Re:Rekurze v Javě (i jinde)
« Odpověď #3 kdy: 19. 11. 2020, 09:19:42 »
Citace: Standa Blábol link=topic=23869.msg340254#msg340254
Nesmysl, na stejne urovni rekurze se spusti se vsechny metody, nebo zadna.

Máš pravdu, taky mi to došlo hned po postnutí a už jsem svůj příspěvek opravil :-)

Re:Rekurze v Javě (i jinde)
« Odpověď #4 kdy: 19. 11. 2020, 09:27:54 »
1. Když píšeš že "to ale funguje v podstatě přesně tak jak bych chtěl. ", tak se mi zdá, že už máš nějaký funkční kód. V takovém případě je asi lepší postnout sem ten, ať neřešíme něco co je třeba jinak.

2. Když už máš funkční kód, doporučuju ti prokrokovat si ho v debuggeru, to ti v tom udělá jasno.

Jinak v postnutém kódu se skutečně vždy spustí buď pouze doSomething(x,y); metoda1(x+1,y), nebo vůbec nic.

Nesmysl, na stejne urovni rekurze se spusti se vsechny metody, nebo zadna.

Presneji, spusti se vsechny metody, ale ty dalsi neudelaji nic, protoze jejich vykonny kod je uvnitr podminky

Kód: [Vybrat]
package testy;

public class Recur {

private boolean podminka = true;

public static void main(String[] args) {
new Recur().go();
}

private void go() {
metoda1(0, 0);
}

public void metoda1(int x, int y) {
System.out.println("metoda1(" + x + "," + y + ")");
if (podminka) {
doSomething(x, y);
metoda1(x + 1, y);
metoda1(x - 1, y);
metoda1(x, y + 1);
metoda1(x, y - 1);
}
}

private void doSomething(int x, int y) {
System.out.println("doSomething(" + x + "," + y + ")");
this.podminka = false;
}

}

Vysledej je podle ocekavani


Kód: [Vybrat]
metoda1(0,0)
doSomething(0,0)
metoda1(1,0)
metoda1(-1,0)
metoda1(0,1)
metoda1(0,-1)




Re:Rekurze v Javě (i jinde)
« Odpověď #5 kdy: 19. 11. 2020, 09:35:05 »
Citace: Standa Blábol link=topic=23869.msg340254#msg340254
Nesmysl, na stejne urovni rekurze se spusti se vsechny metody, nebo zadna.

Máš pravdu, taky mi to došlo hned po postnutí a už jsem svůj příspěvek opravil :-)

Přemýšlím, čím mi ten kód přijde tak matoucí, a asi tím, že aby ta rekurze byla netriviální (tj. `podmínka` se nevyhodnotila vždy jako `false`) a zároveň někdy skončila, musí `metoda1` nebo `doSomething` nějak měnit vnitřní stav a `podmínka` se na ten stav při vyhodnocování odkazovat (což mi přijde ošklivé, i když v nějakém specifickém kontextu to může být dobré řešení). Nebo vás napadá nějaká implementace `podmínka` a `metoda1`, která by se neodkazovala na stav (což dělá třeba `podmínka` u příspěvku Standy Blábola, která je implementovaná jako instanční proměnná), byla netriviální a zároveň někdy skončila? Zas tolik jsem tomu přemýšlení nedal, třeba mi uniká něco očividného..

Re:Rekurze v Javě (i jinde)
« Odpověď #6 kdy: 19. 11. 2020, 09:35:33 »
smazáno

Re:Rekurze v Javě (i jinde)
« Odpověď #7 kdy: 19. 11. 2020, 09:45:36 »
Nikdy se nespustí jen jeden řádek v bloku kódu. Blok kódu se provádí vždy celý od začátku do konce, přerušit jeho provádění může jenom výjimka. (Samozřejmě se bavíme o případu, kdy se blok kódu vůbec má provádět – pokud je ten blok kódu v ifu, provádí se jenom tehdy, když je podmínka splněna.)

Podmínka v ifu se vyhodnotí vždy jen v okamžiku, kdy program tou podmínkou prochází. Když se dodatečně změní proměnná a ten výraz v podmínce by se vyhodnotil jako false, nemá to už žádný vliv. Takže v následujícím kódu se normálně vypíše Hello, World!

Kód: [Vybrat]
boolean priznak = true;
if (priznak) {
  priznak = false;
  System.out.println("Hello World!");
}

Artii

Re:Rekurze v Javě (i jinde)
« Odpověď #8 kdy: 19. 11. 2020, 09:58:14 »
Dobře jedná se o projekt do školy kde máme aplikovat algoritmus seminkového vyplnění rasteru a tím vybarvit veškerou plochu mimo vykreslený obrazec.

Kód: [Vybrat]
private void seedFill(int x, int y){
        if ((bgColor == raster.getPixel(x,y)) && (x>0 && x<799) && (y>0 && y<599)) {
            raster.setPixel(x,y,fillColor);
            seedFill(x + 1, y);
            seedFill(x-1, y);
            seedFill(x, y+1);
            seedFill(x, y-1);

        }

    }
Pokud tedy já zavolám poprvé metodu seedFill (od kliknutí myši) tak program nejprve zkontroluje podmínku:

Kód: [Vybrat]
bgColor == raster.getPixel(x,y)) //zde kontroluje barvu pixelu na pozadí
Kód: [Vybrat]
(x>0 && x<799) && (y>0 && y<599)//zde hranice plátna aby zůstal u vnitř (jinak mi přišlo out of bounds)
pokud je true tak vybarvní pixel dle souřadnic, následně je zavolána ta samá metoda s posunutím o 1 na ose x.

Pokud se během toho posunu dostanu například na hranici nebo na jinou barvu pozadí tak je podmínka v ifu false a celý blok je přeskočen (krokování v debugeru), ale po tom neskončí jak bych očekával ale hned se vrátí zpět a pokračuje další metodou seedFill(x-1,y).

Což vyvolá přesně chování které potřebuji.

Předpokládám že asi bude mít v paměti uložené kde skončil a po vykování toho celého bloku se tedy vrátí zpět. Je to možné?

Re:Rekurze v Javě (i jinde)
« Odpověď #9 kdy: 19. 11. 2020, 10:03:04 »
..Blok kódu se provádí vždy celý od začátku do konce, přerušit jeho provádění může jenom výjimka...

Technická poznámka pro zajímavost: nepokračování bloku kódu může způsobit nejen výjimka, ale i nekonečná rekurze. Např. Scala má typ `Nothing`, který se typicky používá jako typ výsledku funkce, která nikdy neskončí. Implementovat takovou funkci lze jako

def x: Nothing = {
  throw new RuntimeException("Nevratim se")
}

nebo i

def x: Nothing = {
  x
}

Tento typ má docela praktické použití. Jde o typ, který nemá žádnou hodnotu, tj. nelze vytvořit instanci tohoto typu, a je podtypem všech ostatních typů, takže ho lze použít na libovolném místě (v kovariantní pozici) místo jiného typu. Můžu tedy udělat např.

def notImplemented: Nothing = throw new RuntimeException("Not implemented")

val x: Int = if (podmínka) {
 1
} else{
 notImplemented
}

a překladačem to v pohodě projde.

Re:Rekurze v Javě (i jinde)
« Odpověď #10 kdy: 19. 11. 2020, 10:10:07 »
Předpokládám že asi bude mít v paměti uložené kde skončil a po vykování toho celého bloku se tedy vrátí zpět. Je to možné?

Jasně, vykonávaný program má na zásobníku uložené, odkud byla která metoda vyvolaná, a po jejím skončení se vrátí na to místo, rekurze nerekurze. Tvůj semínkový algoritmus mi připadá při rychlém přelétnutí v pohodě, jen by ti při velkém obrázku mohl přetéct zásobník: https://www.tutorialcup.com/interview/stack/recursion.htm

Re:Rekurze v Javě (i jinde)
« Odpověď #11 kdy: 19. 11. 2020, 10:15:00 »
Zřejmě vás mate to, že v debuggeru nevidíte, v kterém volání té funkce jste. Pomůže, když se v debuggeru podíváte na zásobník volání – call stack. Tam uvidíte, jak se vnořujete do volání té funkce a zase vynořujete.

Pokud se během toho posunu dostanu například na hranici nebo na jinou barvu pozadí tak je podmínka v ifu false a celý blok je přeskočen (krokování v debugeru), ale po tom neskončí jak bych očekával ale hned se vrátí zpět a pokračuje další metodou seedFill(x-1,y).
Ono provádění té metody skončí. Ale provádění se tudíž vrátí do místa, odkud byla ta metoda vyvolána. A to místo je shodou okolností zase ta metoda seedFill, ale v předchozí iteraci – právě proto že je to rekurzivní volání.

Tedy vy zavoláte poprvé seedFill. Podmínka se vyhodnotí jak pravdivá, skočí se dovnitř bloku. Následně se zavolá raster.setPixel – zapamatuje se aktuální místo v programu, skočí se do metody setPixel a ta se provádí. Když se dojde na konec metody setPixel, skočí se na zapamatované místo – tedy zpět do prvního volání metody seedFill. Pokračuje se sál, tam je (rekurzivní) volání seedFill – takže se opět zapamatuje aktuální místo a skočí se do metody seedFill – teď už je to druhé zanořené volání. V debuggeru to bude vypadat, že jste najednou skočil na začátek té metody seedFill, ale v zásobníku volání už ta metoda bude dvakrát. Provádí se druhé volání seedFill, v nějakém okamžiku se ukončí a provádění se vrací zpět na zapamatované místo – což je to první volání seedFill. To je to, co vám v debuggeru připadá, jako by byl začátek té metody přeskočen. Ve skutečnosti to ale znamená, že jste se jen vrátil do dříve spuštěné metody a pokračujete tam, kde jste prve skončil. Uvidíte to na zásobníku volání, kde v tu chvíli bude už jenom jedna metoda seedFill – jste zpět v tom prvním volání metody.

Mimochodem, používat na tuhle úlohu rekurzi není moc vhodné. Zásobník volání má omezenou kapacitu, u větších obrázků byste ji překročil.

Artii

Re:Rekurze v Javě (i jinde)
« Odpověď #12 kdy: 19. 11. 2020, 10:15:53 »
Předpokládám že asi bude mít v paměti uložené kde skončil a po vykování toho celého bloku se tedy vrátí zpět. Je to možné?

Jasně, vykonávaný program má na zásobníku uložené, odkud byla která metoda vyvolaná, a po jejím skončení se vrátí na to místo, rekurze nerekurze. Tvůj semínkový algoritmus mi připadá při rychlém přelétnutí v pohodě, jen by ti při velkém obrázku mohl přetéct zásobník: https://www.tutorialcup.com/interview/stack/recursion.htm

Super díky jsem zase o něco chytřejší, šlo mi spíš o to jestli mi někde něco neuniklo a to že to funguje není to jen shoda okolností. Jo to nám ukazoval na přednášce jak ten zásobník vyřešit a taky že toto není moc efektivní varianta ale hezky se na tom ukazuje jak funguje rekurze.

Kit

  • *****
  • 704
    • Zobrazit profil
    • E-mail
Re:Rekurze v Javě (i jinde)
« Odpověď #13 kdy: 19. 11. 2020, 11:57:01 »
Hledej pojem "záplavový algoritmus".

Re:Rekurze v Javě (i jinde)
« Odpověď #14 kdy: 20. 11. 2020, 10:32:49 »
def notImplemented: Nothing = throw new RuntimeException("Not implemented")
Kód: [Vybrat]
???