Fibonacci iteracyjnie a rekurencyjnie - teoria
Fibonacci iteracyjnie a rekurencyjnie - teoria
Witam,
po kilka lekcjach z systemów operacyjnych dostałem za zadanie stworzenie skryptu w bash liczącego n-ty element ciągu Fibonacciego.
Wcześniej nie znałem tego pojęcia, więc poczytałem trochę w sieci teorii i mam zasadnicze pytanie.
O ile ujęcie iteracyjne potrafię zrozumieć (wiem, że trochę się pomęczę ale na pewno jakoś napiszę to przy pomocy pętli for) to nie za bardzo potrafię zrozumieć jak ma w praktyce działać podejście/skrypt rekurencyjny.
Wszędzie zgodnie jest napisane, że jest to prostsza wersja, że funkcja odwołuje się sama do siebie i że wydajnościowo bash ma z tym kłopoty.
Będę bardzo wdzięczny za łopatologiczne wyjaśnienie jak ta rekurencja powinna działać tak abym zrozumiał ideę i miał szansę coś wymyślić w bash:)
Z góry dziękuję.
Pozdrawiam,
Arek
po kilka lekcjach z systemów operacyjnych dostałem za zadanie stworzenie skryptu w bash liczącego n-ty element ciągu Fibonacciego.
Wcześniej nie znałem tego pojęcia, więc poczytałem trochę w sieci teorii i mam zasadnicze pytanie.
O ile ujęcie iteracyjne potrafię zrozumieć (wiem, że trochę się pomęczę ale na pewno jakoś napiszę to przy pomocy pętli for) to nie za bardzo potrafię zrozumieć jak ma w praktyce działać podejście/skrypt rekurencyjny.
Wszędzie zgodnie jest napisane, że jest to prostsza wersja, że funkcja odwołuje się sama do siebie i że wydajnościowo bash ma z tym kłopoty.
Będę bardzo wdzięczny za łopatologiczne wyjaśnienie jak ta rekurencja powinna działać tak abym zrozumiał ideę i miał szansę coś wymyślić w bash:)
Z góry dziękuję.
Pozdrawiam,
Arek
- enedil
- Przebojowy Jelonek
- Posty: 1352
- Rejestracja: 08 wrz 2012, 16:54
- Płeć: Mężczyzna
- Wersja Ubuntu: inny OS
- Środowisko graficzne: i3
- Architektura: x86_64
- Kontakt:
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
Posłużę się przykładem.
Algorytm jedzenia kaszki:
Innymi słowy, wykorzystujesz fakt, że problem można sprowadzić do tego samego dla mniejszych danych, natomiast przypadek bazowy (czyli nie ma już kaszki) powoduje przerwanie swoistej pętli.
Algorytm jedzenia kaszki:
Kod: Zaznacz cały
def jedz_kaszkę(ilość):
jeśli ilość > 0:
jedz_kaszkę(ilość - 1)
Dobrze jest, psiakrew, a kto powie, że nie, to go w mordę!
~moderatorzy
~moderatorzy
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
OK, piszesz jednak o pętli.
Z pętlą kojarzy mi się właśnie iteracyjność.
Gdzie tu zatem ta faktyczna różnica jest między rekurencją a iteracyjnością?
Pozdrawiam,
Arek
Z pętlą kojarzy mi się właśnie iteracyjność.
Gdzie tu zatem ta faktyczna różnica jest między rekurencją a iteracyjnością?
Pozdrawiam,
Arek
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
Podtrzymuję prośbę o wyjaśnienie:)
- valdi74
- Wytworny Kaczor
- Posty: 441
- Rejestracja: 01 maja 2007, 12:58
- Płeć: Mężczyzna
- Wersja Ubuntu: 20.04
- Środowisko graficzne: KDE Plasma
- Architektura: x86_64
- Lokalizacja: Poznań
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
Wykonanie iteracyjne będzie szybsze, ponieważ w rekurencyjnym trzeba wykonać sporo czynności związanych z wywołaniem procedury w każdym obiegu pętli (zapamiętanie adresu/kontekstu na stosie, przekazanie parametrów, alokacja nowych zmiennych lokalnych, itp). Dodatkowo przy bardzo wielu wywołaniach rekurencyjnych może np. zabraknąć pamięci na kolejne zagłębienia. Zaletą rekurencji jest na ogół bardziej czytelny zapis programu niż w przypadku iteracji.
Do poczytania: http://prac.us.edu.pl/~uboryczk/wdi2/pliki/alg/alg4.htm
Do poczytania: http://prac.us.edu.pl/~uboryczk/wdi2/pliki/alg/alg4.htm
Qui vit sans folie, n'est pas si sage qu'on croit
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
OK. dziękuję.
Czyli w kodzie rekurencyjnym też bez pętli nie uda mi się tego zrobić, tak?
Czyli w kodzie rekurencyjnym też bez pętli nie uda mi się tego zrobić, tak?
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
Wracam do tego:)
Iteracyjnie to widzę tak:
a rekurencyjnie mam nadal koncepcyjny kłopot jak do tego podejść:
Zaczałem jak poniżej:
Oczywiście tak liczy mi tylko dla sumy dwóch liczb poprzednich nie odwołując się do tego co było wcześniej.
Jak to naprawić bez posługiwania się pętlą?
Proszę o jakąś wskazówkę.
Pozdrawiam,
Arek
Iteracyjnie to widzę tak:
Kod: Zaznacz cały
echo "Wskaż, dla którego elementu wypisać ciąg Fibonacciego"
read n
if [ $n -le 1 ]; then echo "Wartość ciągu: $n"; fi
x=0
y=1
if [ $n -gt 1 ]; then
for (( i=2; i<=$n; i++))
do
z=$[y+x]
x=$y
y=$z
echo "Wartość ciągu: $z"
done
fi
Zaczałem jak poniżej:
Kod: Zaznacz cały
echo "Podaj liczbę naturalną"
read LICZBA
if [ $LICZBA -le 1 ]; then echo "Liczba Fibonacciego to: $LICZBA"
else
LICZBA=$[($LICZBA - 1) + ($LICZBA - 2)]
echo "Liczba Fibonacciego to: $LICZBA"
fi
Jak to naprawić bez posługiwania się pętlą?
Proszę o jakąś wskazówkę.
Pozdrawiam,
Arek
- enedil
- Przebojowy Jelonek
- Posty: 1352
- Rejestracja: 08 wrz 2012, 16:54
- Płeć: Mężczyzna
- Wersja Ubuntu: inny OS
- Środowisko graficzne: i3
- Architektura: x86_64
- Kontakt:
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
O żadnej pętli nie piszę. Raz jeszcze przeczytaj. Nie ma pętli żadnej. Funkcja wykonuje samą siebie.arhetyp pisze:OK, piszesz jednak o pętli.
Z pętlą kojarzy mi się właśnie iteracyjność.
Gdzie tu zatem ta faktyczna różnica jest między rekurencją a iteracyjnością?
Pozdrawiam,
Arek
Dobrze jest, psiakrew, a kto powie, że nie, to go w mordę!
~moderatorzy
~moderatorzy
- enedil
- Przebojowy Jelonek
- Posty: 1352
- Rejestracja: 08 wrz 2012, 16:54
- Płeć: Mężczyzna
- Wersja Ubuntu: inny OS
- Środowisko graficzne: i3
- Architektura: x86_64
- Kontakt:
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
Bzdury. To nie dlatego złożoność obliczeniowa fib rośnie nagle z O(n^2) do O(2^n). Dobrze zaprojektowany język traktuje rekursję tak samo jak iterację. To przez fakt, że wersja rekurencyjna by obliczyć fib(n+2), nie korzysta z obliczonej wcześniej wartości dla n oraz n+1, tylko liczy na nowo.valdi74 pisze:Wykonanie iteracyjne będzie szybsze, ponieważ w rekurencyjnym trzeba wykonać sporo czynności związanych z wywołaniem procedury w każdym obiegu pętli (zapamiętanie adresu/kontekstu na stosie, przekazanie parametrów, alokacja nowych zmiennych lokalnych, itp). Dodatkowo przy bardzo wielu wywołaniach rekurencyjnych może np. zabraknąć pamięci na kolejne zagłębienia. Zaletą rekurencji jest na ogół bardziej czytelny zapis programu niż w przypadku iteracji.
Do poczytania: http://prac.us.edu.pl/~uboryczk/wdi2/pliki/alg/alg4.htm
Dobrze jest, psiakrew, a kto powie, że nie, to go w mordę!
~moderatorzy
~moderatorzy
- valdi74
- Wytworny Kaczor
- Posty: 441
- Rejestracja: 01 maja 2007, 12:58
- Płeć: Mężczyzna
- Wersja Ubuntu: 20.04
- Środowisko graficzne: KDE Plasma
- Architektura: x86_64
- Lokalizacja: Poznań
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
1. Nie napisałem ani słowa o złożoności fib tylko ogólnie tylko o koszcie wykonania wywołania rekurencyjnego przez procesor. Nie każda wersja rekurencyjna algorytmu ma większą złożoność niż iteracyjna.enedil pisze:Bzdury. To nie dlatego złożoność obliczeniowa fib rośnie nagle z O(n^2) do O(2^n)
2. Złożoność obliczeniowa fib w wersji iteracyjnej to O(n) a nie O(n^2).
Rozumiem, że chodziło Ci o kompilator/interpreter a nie o język? Jakiś przykład takiego kompilatora, który potrafi zamienić każdą rekursję na iterację? O ile mi wiadomo, to w prosty sposób można zamienić na iterację tylko rekursję ogonową.enedil pisze:Dobrze zaprojektowany język traktuje rekursję tak samo jak iterację
Qui vit sans folie, n'est pas si sage qu'on croit
- enedil
- Przebojowy Jelonek
- Posty: 1352
- Rejestracja: 08 wrz 2012, 16:54
- Płeć: Mężczyzna
- Wersja Ubuntu: inny OS
- Środowisko graficzne: i3
- Architektura: x86_64
- Kontakt:
Re: Fibonacci iteracyjnie a rekurencyjnie - teoria
Traktujesz dodawanie jak operację o stałym czasie, prawda? Dla dużych operandów nie jest to prawdą.valdi74 pisze: 2. Złożoność obliczeniowa fib w wersji iteracyjnej to O(n) a nie O(n^2).
1) Nie zaprzeczam istnienia języka, którego specyfikacja o tym wspomina, aczkolwiek to implementację miałem na myśli.valdi74 pisze: Rozumiem, że chodziło Ci o kompilator/interpreter a nie o język? Jakiś przykład takiego kompilatora, który potrafi zamienić każdą rekursję na iterację? O ile mi wiadomo, to w prosty sposób można zamienić na iterację tylko rekursję ogonową.
2) Można dowieść, że nie jest to możliwe dla każdej rekursji.
Dobrze jest, psiakrew, a kto powie, że nie, to go w mordę!
~moderatorzy
~moderatorzy
Kto jest online
Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 29 gości