Fibonacci iteracyjnie a rekurencyjnie - teoria

[arhetyp]

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

[enedil]

Posłużę się przykładem.

Algorytm jedzenia kaszki:

Kod: Zaznacz cały

def jedz_kaszkę(ilość):
    jeśli ilość > 0:
        jedz_kaszkę(ilość - 1)

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.

[arhetyp]

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

[arhetyp]

Podtrzymuję prośbę o wyjaśnienie:)

[valdi74]

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

[arhetyp]

OK. dziękuję.

Czyli w kodzie rekurencyjnym też bez pętli nie uda mi się tego zrobić, tak?

[arhetyp]

Wracam do tego:)

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

a rekurencyjnie mam nadal koncepcyjny kłopot jak do tego podejść:

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

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

[enedil]

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

O żadnej pętli nie piszę. Raz jeszcze przeczytaj. Nie ma pętli żadnej. Funkcja wykonuje samą siebie.

[enedil]

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

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]

Bzdury. To nie dlatego złożoność obliczeniowa fib rośnie nagle z O(n^2) do O(2^n)

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.
2. Złożoność obliczeniowa fib w wersji iteracyjnej to O(n) a nie O(n^2).

Dobrze zaprojektowany język traktuje rekursję tak samo jak iterację

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]

2. Złożoność obliczeniowa fib w wersji iteracyjnej to O(n) a nie O(n^2).

Traktujesz dodawanie jak operację o stałym czasie, prawda? Dla dużych operandów nie jest to prawdą.

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ą.

1) Nie zaprzeczam istnienia języka, którego specyfikacja o tym wspomina, aczkolwiek to implementację miałem na myśli.
2) Można dowieść, że nie jest to możliwe dla każdej rekursji.