Rekurze – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Rekurze – Java – Fórum – Programujte.comRekurze – Java – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
NevimCoSemVyplnit
~ Anonymní uživatel
1 příspěvek
6. 3. 2012   #1
-
0
-

Krásný dobrý den přeju.

Snažim se si nějak nakrokovat jednoduchou metodu, jak ten program vlastně postupuje a například při Fibonacciho posloupnosti se do toho akorát zamotám. Takže máme tu něco takovýho:

static int fib(final int n) {
if (n < 0)
throw new IllegalArgumentException("n < 0");
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}

Dokázal by mi někdo naprosto polopaticky vysvětlit, co se v tý metodě děje? Představuju si to asi následovně: V returnu se zavolá znovu fib o 1 menší argument, pak se zavolá znovu fib o 2 menší argument, teď si ani nedokážu úplně jasně představit, co se stane, ale furt tam vidim snižování pozice, nikoli sčítání dvou předchozích čísel. Tak, kdo to rozčísne? :D

Nahlásit jako SPAM
IP: 88.102.124.–
Reklama
Reklama
liborb
~ Redaktor
+18
Guru
6. 3. 2012   #2
-
0
-
Nahlásit jako SPAM
IP: 78.80.52.–
KIIV+42
God of flame
6. 3. 2012   #3
-
0
-

no vypada to sice jako elegantni zpusob pocitani posloupnosti, ale evidentne je to priserne neefektivni

uz udelat cisla od 0 do 50 trva priserne dlouho (akorat uz se muselo lehce vylepsit na 64b datovy typ - od 47. pozice)

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
liborb
~ Redaktor
+18
Guru
6. 3. 2012   #4
-
0
-

#3 KIIV
Fibonacciho posloupnost je definována rekurzivně, takže tento elegantní způsob se přímo nabízí, a že je to i krásný a odstrašující příklad toho, jak dokáže rekurze devastovat zdroje počítače, je věc druhá.

Nahlásit jako SPAM
IP: 78.80.52.–
KIIV+42
God of flame
6. 3. 2012   #5
-
+1
-
Zajímavé

jedinej zdroj, ktery to devastuje je asi strojovy cas :) pro tech 50 urovni se to nikdy nezanori hloubeji
 

kazdopadne v C tadle mrcha zabira 15minut na 64bitovym procesoru pro posloupnost do 50. prvku

(kdyz sem to udelal sekvencne tak pro 70prvku to vzalo cca 1ms i se spoustenim :) (lepsi rozliseni time nema)

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
liborb
~ Redaktor
+18
Guru
6. 3. 2012   #6
-
0
-

#5 KIIV
Strojový čas je nejvíce vidět, ale paměti požere určitě taky dost. Rozhodně mnohonásobně víc než sekvenční :).

Nahlásit jako SPAM
IP: 78.80.52.–
sleepy0
Stálý člen
9. 3. 2012   #7
-
0
-

Jednoducho return caka na nieco co moze odoslat, co je v tomto pripade (fib(n-1)+fib(n-2)). Cize caka kym sa vypocita fib(n-1) a fib(n-2), spocita ich a odosle.

Inak pre o nieco malo rychlejsi vypocet clenov Fibbonacciho postupnosti existuje taky rekurentny vzorec : fib(n):=(1/sqrt(5))*(((1+sqrt(5))/2)^n+((1-sqrt(5))/2)^n)

Nahlásit jako SPAM
IP: 213.215.67.–
pidgin0
Návštěvník
11. 3. 2012   #8
-
0
-

#1 NevimCoSemVyplnit
Myslím, že tazatel nedostal odpověď na svojí otázku: co a jak to vlastně dělá a kdy se to začne sčítat. Zkus si to představit jako funkce jež volá v návratu dvě funkce a postupně se to větví. Mě se velmi osvědčilo nakreslení si toho na papír. Vytváří se (pomocí exekučních zásobníků) takzvaný "binární strom" a až to dojede na dno (if==0 nebo if==1) tak se to začne vracet zpátky a teprve tehdy se začnou sčítat ty returny ( return 0 a return 1). Tedy: nakreslit si to na papír a pak nad tím chvíli dumej a ono to pude :-) zdravím

Nahlásit jako SPAM
IP: 78.102.86.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 29 hostů

Podobná vlákna

Rekurze — založil johny

Rekurze — založil CML

Rekurze SPĚCHÁ — založil Hanmir1

Nalezení rekurze — založil sh00ter

Použití rekurze — založil ST33L

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý