C++, przykład funkcji rekurencyjnej

Question

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

Answer 1

Tyle kresek co wrzuciłeś to za dużo na moją głowę. Zobacz na listing niżej, zmniejszyłem liczbę kresek i trochę mi się rozjaśniło :)

|               | <- start
|       |       | <- poziom 1.
|   |   |   |   | <- poziom 2.
| | | | | | | | | <- poziom 3.
0 1 2 3 4 5 6 7 8

Tablica do przechowania takiego stringa potrzebuje mieć rozmiar 10 (9 kresek + '\0'). Na starcie na pozycje min(0) i max(8 = 10 - 2) wpisywane są kreski (zobacz u siebie w kodzie linijka 27.).

(...) ilość działających w tle wywołujących się funkcji rośnie geometrycznie. Mamy 6 poziomów a 2^6 wynosi 64 (...)

•  Gdy jesteśmy na poziomie 1 odpalamy 1 funkcję.
•  Gdy jesteśmy na poziomie 2 odpalamy 2 kolejne funkcje (mamy już w sumie 3).
•  Gdy jesteśmy na poziomie 3 odpalamy 4 kolejne funkcje (mamy już w sumie 7).

Więc na 3 poziomy rekurencji, a wywołaliśmy 7 funkcji. Można by to policzyć ze wzoru: 2^poziom - 1.

Podsumowując: tablica 10 elementów = 2 (min i max) + 7 (funkcje rekurencyjne) + 1 ('\0'). Mógłbyś rozmiar potrzebnej tablicy wyliczać tak:

const int Divs = 3; //poziomy
const int Len = 2 + pow(2, Divs)-1 + 1; //musi być podzielna przez 2

Comments

Dzięki, zwłaszcza za wzór. Przyda mi się :)