Rekurencyjne sumowanie liczb w tablicy - gubię dane

[Antystatyczny]

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:

Kod: Zaznacz cały

/* Cwiczenie rekurencji
 * Moim zadaniem jest zsumowanie wszystkich komórek tablicy
 */

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

int suma(const int *src, size_t length, int sum)
{
   if (length)
   {
      return suma( (src + 1), --length, (sum + *src)  );
   }
   
   return *src + sum;
}

int sumujTablice(const int* tab, size_t len)
{
   return  suma(tab, len - 1, 0);//pierwszy poziom rekurencji
}


int main(void)
{
   int tablica[] = { 8, 13, 15, 20 };

   printf("Suma liczb w tablicy wynosi %d\n", sumujTablice(tablica, sizeof(tablica) / sizeof(tablica[0]) ) );

   int key = getchar();
   return EXIT_SUCCESS;
}

Dzięki za pomoc i wspólne myślenie!

[dambo]

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?

[mokrowski]

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;
}

[Antystatyczny]

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

[dambo]

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

[mokrowski]

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

[Antystatyczny]

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

Kod: Zaznacz cały

/* Ćwiczenie rekurencji. Przekazac do funkcji wskaźnik na tablicę,
   jej rozmiar, oraz funkcję wartościującą poszczególne komórki tablicy.
*/

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


typedef bool (filterTableFunType)(int * src);

/* funkcje wartościujące */
bool isOdd(int *src)
{
   return (*src & 0x01);
}

bool isEven(int * src)
{
   return ( !(*src & 0x01) );
}


/* funkcja rekurencyjna */
void filter(int *src, size_t len, filterTableFunType * fun)
{
   if (len > 0)
   {
      /* zeruj komórkę jeśli funkcja wartościująca zwróciła true */
      if (fun(src) != false )
      {
         *src = 0;
      }
            
      filter(++src, --len, fun);
   }

   return;
}

int main(void)
{
   int daneWejsciowe[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
   

   /* Wycinanie wszystkich wartości parzystych */
   filter(daneWejsciowe, 20, isEven);

   /* Wycinanie wszystkich wartości nieparzystych */
   //filter(daneWejsciowe, 20, isOdd);


   /* Prezentacja danych po zastosowaniu wybranego filtru. */
   for (int i = 0; i < 20; ++i)
   {
      printf("Zawartosc komorki o indeksie %d: %d\n", i, daneWejsciowe[i]);
   }

   int key = getchar();

   return EXIT_SUCCESS;
}

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.

[szafarz]

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

[mokrowski]

@szafarz uważnego czytania przykładów w wątku życzę