Prośba o wytłumaczenie przykładu z rekurencji - podziałka (Stephen Prata - Język C++)

0

Witajcie. Czy ktoś z życzliwych doświadczonych bardziej niż ja w nauce programowania forumowiczów mógłby mi wyjaśnić przykład ze strony 324 książki wymienionej w tytule wątku? Rozumiem generalnie o co chodzi w rekurencji (a przynajmniej tak mi się wydaje ;) , ale nie jest dla mnie jasne, dlaczego w wywołaniach funkcji subdivide w nawiasie podane jest "level -1"; przecież jeśli w pętli for w mainie zaczynamy od i=1, to powinno to zmieniać i na zero, co w kolejnym wywołaniu oznacza komendę return? I gdzie tu rekurencja? :/ Czy może ktoś jakoś jaśniej rozpisać mi, co się po kolei dzieje w każdej iteracji? Czy nie powinno raczej i zmieniać się od 6 do zera i potem return...? Wszystko się kręci :D

0

Byłoby miło, gdybyś pokazał nam ten kod. Nie wszyscy mamy pod ręką tę księżkę.

0
#include <iostream>
#include <iostream>

const int Len=66;
const int Divs = 6;
void subdivide (char ar[], int low, int high, int level);

int main ()
{
    char ruler [Len];
    int i;
    for (i=1; i<Len; i++)
      ruler [i] = ' ';
    ruler[Len-1] = '\0';
    int max = Len-2;
    int min = 0;

    ruler[min] = ruler[max] = '|';
    std::cout<<ruler<<std::endl;

    for (i=1; i<Divs; i++)
    {
        subdivide(ruler,min,max,i);
        std::cout<<ruler<<std::endl;

        for (int j=1; j<Len-2; j++)
            ruler[j]=' ';  //zerowanie linijki

    }
        return 0;
}


void subdivide(char ar[], int low, int high, int level)
{
    if (level==0)
        return;
    int mid = (high+low)/2;
    ar[mid] = '|';
    subdivide(ar,low,mid,level-1);
    subdivide(ar,mid,high,level-1);
}

0
higgsboson napisał(a):

Rozumiem generalnie o co chodzi w rekurencji (a przynajmniej tak mi się wydaje ;) , ale nie jest dla mnie jasne, dlaczego w wywołaniach funkcji subdivide w nawiasie podane jest "level -1"; przecież jeśli w pętli for w mainie zaczynamy od i=1, to powinno to zmieniać i na zero, co w kolejnym wywołaniu oznacza komendę return? I gdzie tu rekurencja? :/ Czy może ktoś jakoś jaśniej rozpisać mi, co się po kolei dzieje w każdej iteracji? Czy nie powinno raczej i zmieniać się od 6 do zera i potem return...? Wszystko się kręci :D

Na poziomie i = 1, czyli w pierwszym elemencie linijki, masz mieć kreskę pionową na samej górze na obu krańcach. Zwróć uwagę, że potem w pętli przechodzisz do i = 2, itd.
Zresztą - rekurencja sprowadza się do wywołania funkcji w funkcji i ta zasada jest spełniona nawet dla level - 1.

Osobiście uważam, że to jest najmniej trafiony przykład w książce.

Silnia, potęgowanie i fibbonacci tłumaczą to dużo lepiej:
http://cpp0x.pl/kursy/Kurs-C++/Poziom-5/Rekurencja/585

0

Próbuję to rozgryźć już któryś raz i nadal nie rozumiem 'level -1', dla mnie to oznacza że 1-1 =0 i powinna się zakończyć rekurencja, nie wiem jak mam to zrozumieć.
Przykład z silnią, ciągiem Fibonacciego i potęgami rozumiem, ale to są funkcje które zwracają wartość (po napotkaniu przypadku podstawowego) do funkcji wyżej, i tamta funkcja przekazuje to wyżej itd - to jest logiczne. Ale tutaj nie ma zwracania wartości, jest kolejny podział dla level-1, czyli 0.
Chyba dam sobie spokój :/

0

No i ma się zakończyć, zgodnie z tym co mówiłem. W następnym obiegu pętli, i = 2, więc level - 1 = 1, wywołanie będzie raz.

PAtrz na komentarze:

void subdivide(char ar[], int low, int high, int level) //argumenty na start ruler,min,max,i, gdzi i = 1;
{
    if (level==0) //sprawdza warunek, level == i == 1; zatem if pominięty idziemy dalej
        return;
    int mid = (high+low)/2; //wykonuje się
    ar[mid] = '|'; // wykonuje się
    subdivide(ar,low,mid,level-1); // rekurencyjne wywolanie funkcji, wiec level dla tego cyklu wyniesie 0, zatem wywolanie funkcji zamknie się po napotkaniu instrukcji if (level == 0) i przejdzie do nastepnej linii
    subdivide(ar,mid,high,level-1); // jak wizen
}

Weź sobie tu podstawiaj kolejno za i, patrząc na to co napisałem.

0

Wbrew pozorom rekurencja nie jest prosta, a Twój przykład także do najprostszych nie należy. Spróbuj przeanalizować jak działa taki kod (Python):

a = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

def sum_rek(a):
    if len(a) == 1:
        return a[0]
    n = len(a) // 2
    return sum_rek(a[:n]) + sum_rek(a[n:])

print(sum_rek(a))
  1. Najpierw odpal sobie w Ideone, jak nie łapiesz, to wyprintuj sobie poszczególne etapy liczenia.
  2. Spróbuj napisać kod dla listy o na przykład dziesięciu elementach.
  3. Spróbuj napisać kod równoważny w Twoim języku, czyli C++ i w dalszym ciągu przeglądaj poszczególne kroki liczenia.

To na razie tyle, łatwiej chyba nie dam rady, ale skoro łapiesz Fibonnaciego (nie pytam w jakiej wersji), to powinieneś załapać, prędzej czy później :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1