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
Byłoby miło, gdybyś pokazał nam ten kod. Nie wszyscy mamy pod ręką tę księżkę.
#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);
}
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
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 :/
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.
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))
- Najpierw odpal sobie w Ideone, jak nie łapiesz, to wyprintuj sobie poszczególne etapy liczenia.
- Spróbuj napisać kod dla listy o na przykład dziesięciu elementach.
- 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 :)