Witam, zaraz pokażę kod i wynik działania pewnej funkcji wykorzystującej rekursje. Ogólnie rozumiem zasadę jej działania ale mam problem ze zrozumieniem jednego szczegółu samego programu:
#include <iostream>
const int Len = 66; //musi być podzielna przez 2
const int Divs = 6; //poziomy
void subdivide(char ar[], int low, int hight, int level) {
if (level == 0) return;
int mid = (hight + low) / 2;
ar[mid] = '|';
subdivide(ar, low, mid, level - 1);
subdivide(ar, mid, hight, level - 1);
}
int main(){
char ruler[Len];
int i;
int max = Len - 2; //-2 bo -1 to NUL
int min = 0;
for (i = 1; i < max; i++) //mniej od Len-2 bo konec to NUL aprzed koncem jeszcze znak '|'
ruler[i] = ' ';
ruler[Len - 1] = '\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 < max; j++)
ruler[j] = ' ';
}
return 0;
}
Wynik działania jest następujący:
const int Len = 66;
Długość to myślę że sprawa zrozumiała, mamy 66 znaków w tym jeden na NUL a więc 65, czyli indeksy tej tablicy znaków są w zakresie od 0-64
const int Divs = 6;
Poziomy, ilość wywołań rekurencyjnych by zapełnić cały łańcuch znakami '|'. Korzystamy z metody dziel i zwyciężaj więc ilość działających w tle wywołujących się funkcji rośnie geometrycznie. Mamy 6 poziomów a 2^6 wynosi 64 a więc jest to liczba potrzebna by zapełnić cały łańcuch tymi znakami. Tu jest problem, książka z której korzystam upiera się że mamy 64 pól do zapełnienia więc liczba 6 jest poprawna (i jest poprawna w działaniu). Jednak ja tu czegoś nie rozumiem:
Mamy łańcuch który mieści 65 znaków a nie 64 (66 - 1 na NUL = 65), według mnie to się nie zgadza. To fakt że 2 elementy tablicy są już z góry zapełnione, indeks zerowy i 64 a więc w sumie pozostaje nam 63 pola do zapełnienia. Teraz za to ta liczba wydaja się za mała...
Z góry dziękuje za pomoc, jestem dość słaby z matmy i to może mieć wpływ :/