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

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

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

Ok, mam! oczywiście mój tok myślenia był błędny, dlatego program w tej formie nie mógł działać poprawnie. Oczywiście miałeś rację pisząc, że niezależnie od tego, co się działo wewnątrz instrukcji warunkowej, wynikiem działania programu była suma dwóch pierwszych komórek. Rozrysowałem sobie te skoki na kartce i OCZYWISTE jest, że musi być return suma(...); Przecież mnie interesują wyniki działania poszczególnych poziomów, a kompilator jedynie zoptymalizuje powrót z ostatecznym wynikiem. Przy okazji znalazłem błąd polegający na wywoływaniu rekurencji o jeden raz za dużo. Oto finalna i działająca wersja:

Ukryta zawartość
To forum wymaga zarejestrowania i zalogowania się, aby zobaczyć ukrytą zawartość.


Dzięki za pomoc i wspólne myślenie! :)
"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:32

super :) funkcja teraz działa, ale chyba nie uzyskaliśmy efektu ogonowości:
aaaaaaa.png


w call stacku widzimy wywołania poszczególnych, może trzeba to jakoś inaczej sprawdzać i w debugu zawsze to tak wygląda?
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
mokrowski
User
User
Posty: 190
Rejestracja: czwartek 08 paź 2015, 20:50
Lokalizacja: Tam gdzie Centymetro

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: mokrowski » wtorek 21 mar 2017, 21:34

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>

int recur_sum(int * table, size_t last_elem_index, int sum) {
    sum += table[0];
    return !last_elem_index ? sum : recur_sum(++table, --last_elem_index, sum);
}

int main(void) {
    int table[] = {1, 2, 3, 10, 20};
    size_t table_length = sizeof(table) / sizeof(table[0]);
    printf("Suma wynosi: %d\n", recur_sum(table, table_length - 1, 0));

    return EXIT_SUCCESS;
}
,,Myślenie nie jest łatwe, ale można się do niego przyzwyczaić" - Alan Alexander Milne: Kubuś Puchatek

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:35

Moim zdaniem jest ogonowa... Zerknij na drzewo wywołań. Widać kilka rekurencji, a następnie powrót do main. A może ja to źle odczytuję? Z tym debuggerem w VS jeszcze sobie nie radzę.
"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:41

nie nie - odwrotnie - to znaczy, ze main ją wywołał.

ale w przykładzie kolegi mokrowskiego też tak jest - więc pewnie ja źle debuguje - umieszczam point w return sum i i tak schodzi kolejno, a nie bezpośrednio do maina
Nowy blog o tematyce embedded -> https://www.embedownik.pl/

Awatar użytkownika
mokrowski
User
User
Posty: 190
Rejestracja: czwartek 08 paź 2015, 20:50
Lokalizacja: Tam gdzie Centymetro

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: mokrowski » wtorek 21 mar 2017, 21:43

@dambo ja nie wiem czy VS ma możliwość kompilacji z debug i równocześnie choćby małej optymalizacji. Jeśli nie uruchomisz choćby podstawowej optymalizacji, nie będziesz miał tail. Zapraszam szybciutko na chat a zobaczysz dlaczego.
,,Myślenie nie jest łatwe, ale można się do niego przyzwyczaić" - Alan Alexander Milne: Kubuś Puchatek

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 » środa 22 mar 2017, 17:55

Idąc za ciosem napisałem filtr rekurencyjny. Temat ćwiczenia podsunął mi Mokrowski, a implementacja jest moja własna. Oto program:

Ukryta zawartość
To forum wymaga zarejestrowania i zalogowania się, aby zobaczyć ukrytą zawartość.



Można sobie wybrać jedną z dwóch opcji (ewentualnie obie jednocześnie - wtedy odfiltruje każdą wartość). Wartość początkowa elementów tablicy jest widoczna, a dane wyjściowe są prezentowane w konsoli.
"The true sign of intelligence is not knowledge but imagination" Albert Einstein.

szafarz
Posty: 5
Rejestracja: piątek 08 wrz 2017, 01:41

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: szafarz » piątek 08 wrz 2017, 03:26

Może i późno tu zajrzałem, ale lepiej późno niż wcale. To nie jest rekurencja ogonowa, bo każda funkcja zwraca wartość. Zastanów się dlaczego. Dla ułatwienia zmień kod tak (to tylko istotny fragment):

Kod: Zaznacz cały

   suma( src, length, sum  );//kolejne poziomy rekurencji
   } else
   
   /* Ostatnim poleceniem ma być wywołanie rekurencyjne lub powrót z funkcji.
    * Tylko wtedy funkcja będzie mogła być ogonowa. */

   return sum;
}


Jak sam napisałeś w komentarzu:
/* Ostatnim poleceniem ma być wywołanie rekurencyjne lub powrót z funkcji.


Życze dalszego miłego zgłębiania tajników programowania

Awatar użytkownika
mokrowski
User
User
Posty: 190
Rejestracja: czwartek 08 paź 2015, 20:50
Lokalizacja: Tam gdzie Centymetro

Re: Rekurencyjne sumowanie liczb w tablicy - gubię dane

Postautor: mokrowski » piątek 08 wrz 2017, 13:58

@szafarz uważnego czytania przykładów w wątku życzę :-)
,,Myślenie nie jest łatwe, ale można się do niego przyzwyczaić" - Alan Alexander Milne: Kubuś Puchatek


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 1 gość