Rekurze – Java – Fórum – Programujte.com

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

Příklad i s ukázkou

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)

#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á.

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)

#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í :).

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)

#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