Strona 1 z 2
Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 18:34
autor: Antystatyczny
Witam serdecznie.
Siedzę nad funkcjami rekurencyjnymi, a konkretnie rekurencjami ogonowymi. Moim zadaniem jest zsumowanie wszystkich liczb znajdujących się w tablicy. O ile iteracyjna wersja funkcji nie sprawiła mi najmniejszy problemów, tak rekurencyjna robi ze mną co tylko zapragnie. Napisałem taki oto programik ćwiczebny:
Ukryta zawartość
To forum wymaga zarejestrowania i zalogowania się, aby zobaczyć ukrytą zawartość.
A to jest wynik działania programu:
Ukryta zawartość
To forum wymaga zarejestrowania i zalogowania się, aby zobaczyć ukrytą zawartość.
Program brnie w kolejne poziomy rekurencji i prawidłowo sumuje wartości kolejnych komórek tablicy. Jednak podczas powrotu dzieje się coś niedobrego (i tu właśnie nie wiem co) i program kończy działanie zwracając jedynie sumę dwóch pierwszych komórek tablicy.
Szczerze mówiąc nie bardzo widzę, gdzie popełniam błąd. Chętnie przyjmę jakąś pomoc w rozwiązaniu tego problemu
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:29
autor: dambo
a sum nie powinien być też wskaźnikiem? nic nie zwracasz teraz z funkcji praktycznie oprócz sumy dokładnie *scr - czyli drugiego obiektu (bo inkrementujesz) i sum - wartości 1 obiektu
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:34
autor: Antystatyczny
Każdy kolejny poziom rekurencji ma pracować na własnym komplecie argumentów, dlatego sum nie jest wskaźnikiem. A co do zwracania... Dopiero ostatni poziom rekurencji ma zwrócić sumę wszystkich pośrednich poziomów + zawartość ostatniej komórki tablicy. Na tym polega rekurencja ogonowa, że wracam bezpośrednio do miejsca wywołania pierwszego poziomu - bez powrotów przez wszystkie poziomy.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:37
autor: dambo
no ale gdzie jest tu mechanizm zwrotu wartości z tej ostatniej funkcji, bo nie mogę tego załapać? Obecnie zadziała to tak jak napisałem - tylko pierwsze wywołanie coś robi, reszta się robi bez zwracania czegokolwiek
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:40
autor: Antystatyczny
Zgadza się... pośrednie nie zwracają wartości, bo przekazują obliczoną sumę z aktualnego poziomu do poziomu niżej.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:43
autor: dambo
ok, za pomocą czego ją przekazują? Która linijka dokładnie to robi?
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:47
autor: Antystatyczny
Tutaj masz rekurencyjne wywołanie funkcji wraz z zaktualizowaną wartością zmiennej 'sum' oraz 'length'. Oczywiście wskaźnik na tablicę również jest zwiększony o 1, co widać wewnątrz instrukcji warunkowej:
Ukryta zawartość
To forum wymaga zarejestrowania i zalogowania się, aby zobaczyć ukrytą zawartość.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:53
autor: dambo
no dobrze, wiec przekazujesz ją tak, zmienne są kopiowane, nowa funkcja suma ma swoją kopie zmiennych, a pierwsza funkcja i tak zwraca swoje (te pierwsze 2 elementy)
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 19:55
autor: Antystatyczny
No właśnie pierwsza funkcja w ogóle nie wraca. Wraca tylko ta ostatnia od razu na samą górę. Na tym polega działanie rekurencji ogonowej. Coś jednak robię źle, bo wynik jest błędny.
A właściwie nie powinna wrócić. Możliwe, że jest właśnie tak, jak piszesz...ale to jest błędne działanie (odmienne od zamierzonego).
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:00
autor: dambo
może głupie pytanie, ale dalej nie widzę tu tego mechanizmu, że ostatnia tylko zwraca - jak wywołasz pierwszą funkcję to dojedzie do wywołania kolejnej itd, ale ona i tak wróci do "siebie" i wykona się na końcu ten return sumy dwóch pierwszych elementów
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:02
autor: Antystatyczny
Kompilator, przy prawidłowo napisanej rekurencji ogonowej, optymalizuje kod i standardowe wywołania funkcji (zapamiętanie adresu powrotu itd.) zastępuje zwykłym skokiem na początek funkcji. To pozwala na obniżenie zużycia stosu, bo zapamiętywany jest jedynie adres powrotu do miejsca pierwszego wywołania funkcji.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:05
autor: dambo
żeby był porządek, bo edytowałem przed twoim postem, skasuje tamten edit:
Kod: Zaznacz cały
suma( src, length, sum );//kolejne poziomy rekurencji
nie powinno być return przed?
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:07
autor: Antystatyczny
Nie, bo wtedy byłaby to zwykła rekurencja, czyli funkcje kolejno wracałyby na wyższe poziomy zwracając wynik działania.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:13
autor: dambo
ok, z tego co znalazłem na temat rekurencji ogonowej jest to, że funkcja powinna być zwracana na końcu, a jeśli jest to "ostatnie ogniwo" to przed. przykład:
Kod: Zaznacz cały
public static long fib(int n, long a, long b)
{
// short: return n == 0 ? b : fib(n - 1, a + b, a);
if (n == 0)
{
return b;
}
return fib(n - 1, a + b, a);
}
wzięte z tej stronki -
https://blog.gutek.pl/2016/10/24/rekure ... malizacja/Edit:
Kompletnie nie znałem tego mechanizmu, więc sorki za wcześniejsze błędne sugestie. Fajne jest, że to kompilator sam stwierdzi, o tym, ze jest to funkcja ogonowa i tu mi się nasuwa jedna rzecz - zakomentuj wyświetlanie w środku - może kompilator uważa to za coś ważnego, że musi się zawsze wykonać i dlatego nie robi rek ogonowej z tego, ale to pewnie też ślepy strzał.
Ale jak widzisz przy wywołaniu kolejnej funkcji ze środka jednak jest return
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:21
autor: Antystatyczny
Ten printf wsadziłem w akcie desperacji, bo już nie miałem innych pomysłów. Chciałem podejrzeć, co się dzieje z wartościami. Z książki "Język C: Szkoła programowania" Stephen Prata (wydanie VI), strona 382, dowiaduję się, że funkcja ogonowa jest wtedy, gdy wywołanie rekurencyjne następuje tuż przed instrukcją return. U mnie właśnie tak jest... Ostatnia instrukcja przed powrotem to właśnie wywołanie rekurencyjne. Jeżeli warunek stopu zostaje spełniony, czyli length == 0, rekurencja ulega przerwaniu i ma nastąpić bezpośredni powrót na samą górę poprzez pojedynczą instrukcję return. Dopiero raczkuję w tym temacie, więc być może coś jeszcze źle rozumiem i dlatego popełniam błąd.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:26
autor: dambo
a jaki będziesz miał sposób na sprawdzenie, czy faktycznie zrobiła się rekurencja ogonowa, czy zwykła?
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:29
autor: Antystatyczny
Mam przekazywać do kolejnych poziomów narastającą sumę komórek, a powrót z ostatniej funkcji ma zwrócić sume wszystkich komórek. Wtedy będę wiedział, że jest ogonowa. Można również podejrzeć kod wynikowy, ale na PC się za to nie zabieram. Pewnie łatwiej byłoby mi to podejrzeć uruchamiając ten program np. na AVR czy ARM
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:36
autor: dambo
w "Język C: Szkoła programowania" Stephen Prata (wydanie V) - też jest zawsze return przed wywołaniem kolejnej funkcji w rekurencji
Tzn ja to rozumiem tak, robimy funkcję rekurencyjną, jeśli ją odpowiednio napiszemy, to kompilator rozpozna, że ma zrobić rekurencję ogonową. No ale w twoim przypadku skoro tam nie ma return przed wywołaniem, to nie jest rekurencja, więc kompilator wcale nie będzie tego tak rozpatrywał (no i to potwierdza działanie programu).
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:43
autor: Antystatyczny
Masz na myśli program obliczający silnię rekurencyjnie i iteracyjnie? W tym programie faktycznie jest użyty return z każdego poziomu rekurencji.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:46
autor: Antystatyczny
dambo pisze:No ale w twoim przypadku skoro tam nie ma return przed wywołaniem, to nie jest rekurencja, więc kompilator wcale nie będzie tego tak rozpatrywał (no i to potwierdza działanie programu).
W takim razie kompletnie nie rozumiem, jak ma działać rekurencja ogonowa.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:54
autor: dambo
chodzi mi o to, że kompilator widzi jakąś funkcję, sprawdza, czy jest rekurencyjna i jeśli jest to jeśli jest odpowiednio napisana może ją zinterpretować jako rekurencję ogonową.
No ale w twoim przypadku, skoro nie ma return to kompilator poprawnie stwierdza, ze to nie jest rekurencja, bo teraz wywołujesz tą funkcję dając informację, że nie interesuje Cię co ona zwróci. Więc jej działanie jest dokładnie takie jak w kodzie - wchodzi pierwszy raz, robi swoje operacje, potem wywołuje kolejny raz siebie, ale nie chce od niej nic, więc te funkcje się robią, nie zwracając rezultatów do tych niżej i na końcu pierwsza wywołana funkcja zwraca sumę dwóch elementów.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:55
autor: Antystatyczny
...ale funkcja zwróci wynik, jeśli wykorzystać zwracanie wartości, do funkcji na wyższym poziomie, a nie na niższym... Schodzimy w dół wywołując kolejno tę samą funkcję.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 20:59
autor: dambo
Antystatyczny pisze:...ale funkcja zwróci wynik, jeśli wykorzystać zwracanie wartości, do funkcji na wyższym poziomie, a nie na niższym... Schodzimy w dół wywołując kolejno tę samą funkcję.
nie rozumiem tego zdania, możesz to inaczej ubrać w słowa?
Edit:
tutaj znalazłem fajny przykład:
http://stackoverflow.com/questions/1551 ... rsion-workże kompilator rekurencję ogonową zamienia w zwykłą pętle. No ale dalej wracamy do tego, że musi tam być return przy wywołaniu kolejnej.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 21:03
autor: Antystatyczny
Schodzenie niżej realizujemy poprzez kolejne wywołania funkcji (rekurencyjne wywołania), a powroty w górę realizujemy zwracając wynik działania funkcji na jakimś poziomie do poziomu wyżej.
Tak czy siak uważam, że jeśli ma to być rekurencja ogonowa, nie powinienem zwracać wyniku przez wszystkie poziomy rekurencji.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
: wtorek 21 mar 2017, 21:10
autor: dambo
no ale jak jest podane w linku wyżej - to jest taka forma zapisu że kompilator uprości to sobie do pętli, ale bez tego return on nie wie, że chcesz rekurencje. Cytat ze stackoverflow:
Kod: Zaznacz cały
// tail recursion
int fac_times (int n, int acc = 1) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
would compile to something like
Kod: Zaznacz cały
// accumulator
int fac_times (int n) {
int acc = 1;
while (n > 0) {
acc *= n;
n -= 1;
}
return acc;
}
Ale idąc tym tropem - ciekawe, czy ktoś miał taki problem, ze musiał mieć rekurencję zwykłą, a kompilator robił ogonową (ale kompletnie nie znam zastosowania dla tego :p )