Rekurencyjne sumowanie liczb w tablicy - gubię dane
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Rekurencyjne sumowanie liczb w tablicy - gubię dane
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:
A to jest wynik działania programu:
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
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:
A to jest wynik działania programu:
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
ok, za pomocą czego ją przekazują? Która linijka dokładnie to robi?
Nowy blog o tematyce embedded -> https://www.embedownik.pl/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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:
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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).
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
żeby był porządek, bo edytowałem przed twoim postem, skasuje tamten edit:
nie powinno być return przed?
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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:
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
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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).
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
...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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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/
- Antystatyczny
- Geek
- Posty: 1168
- Rejestracja: czwartek 03 wrz 2015, 22:02
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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.
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.
Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane
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:
would compile to something like
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 )
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 3 gości