Rekurencyjne sumowanie liczb w tablicy - gubię dane

W tym miejscu zadajemy pytania na temat języka C, dzielimy się swoją wiedzą, udzielamy wsparcia, rozwiązujemy problemy programistyczne.
Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 18:34

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 :)
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 19:29

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
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 19:34

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.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 19:37

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
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 19:40

Zgadza się... pośrednie nie zwracają wartości, bo przekazują obliczoną sumę z aktualnego poziomu do poziomu niżej.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 19:43

ok, za pomocą czego ją przekazują? Która linijka dokładnie to robi?
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 19:47

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ść.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 19:53

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)
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 19:55

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).
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 20:00

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
Ostatnio zmieniony wtorek 21 mar 2017, 20:05 przez dambo, łącznie zmieniany 2 razy.
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 20:02

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.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 20:05

ż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?
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 20:07

Nie, bo wtedy byłaby to zwykła rekurencja, czyli funkcje kolejno wracałyby na wyższe poziomy zwracając wynik działania.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 20:13

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
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 20:21

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.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 20:26

a jaki będziesz miał sposób na sprawdzenie, czy faktycznie zrobiła się rekurencja ogonowa, czy zwykła?
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 20:29

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
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 20:36

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).
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 20:43

Masz na myśli program obliczający silnię rekurencyjnie i iteracyjnie? W tym programie faktycznie jest użyty return z każdego poziomu rekurencji.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 20:46

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.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 20:54

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.
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 20:55

...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ę.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 20:59

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.
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
Antystatyczny
Geek
Geek
Posty: 1168
Rejestracja: czwartek 03 wrz 2015, 22:02

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: Antystatyczny » wtorek 21 mar 2017, 21:03

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.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

Awatar użytkownika
dambo
Expert
Expert
Posty: 645
Rejestracja: czwartek 17 mar 2016, 17:12

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: dambo » wtorek 21 mar 2017, 21:10

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 )
Nowy blog o tematyce embedded -> https://www.embedownik.pl/


Wróć do „Pisanie programów w C”

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 4 gości