Trzeci algorytm rozwiązywania problemu min-max, to algorytm rekurencyjny. Z zasadą "dziel i zwyciężaj", którą tu wykorzystano spotkaliśmy w wcześniej w algorytmie binarnych poszukiwań. Warto ją zapamiętać, gdyż będzie jeszcze wielokrotnie wykorzystywana. Zasada ta głosi, że aby rozwiązać zadanie rozmiaru n należy najpierw podzielić je na podzadania o mniejszych rozmiarach ( np. na dwa podzadania rozmiaru n/2), rozwiązać je i z uzyskanych rozwiązań podzadań wywnioskować rozwiązanie końcowe.

W konkretnym przypadku problemu min-max, zastosowanie zasady "dziel i zwyciężaj" będzie polegało na podzieleniu danych na dwie, możliwie równe części, znalezienie elementów największego i najmniejszego w każdej z nich, a następnie ustalenie elementu najmniejszego całego ciągu, przez porównanie wybranych elementów najmniejszych i ustalenie elementu największego przez porównanie elementów największych każdej z dwóch części:

Algorytm zostanie zapisany jako funkcja min_max3, która zwraca obiekt typu para o dwóch atrybutach min i max. Funkcja ta ma trzy parametry, którymi są: dany ciąg oraz dwa indeksy wskazujące początek i koniec rozważanego fragmentu tego ciągu. W pierwszym wykonaniu funkcji te parametry powinny mieć odpowiednio wartości 1 i n. Dla uproszczenia rozważań, przyjmijmy, że n (tzn. liczba elementów w ciągu) jest potęgą 2.

gdzie min(e) oznacza element najmniejszy, a max(e) - element największy w ciągu e.

para	min_max3 (e: ciąg, i, j : int);
	if (i+1=j) then
	if e[i] £ e[j] then
	result.min := e[i]; result.max := e[j];
	else
	result.min := e[j]; result.max := e[i];
	fi
	else
	x := min_max3 (e, i, (i+j)div 2);	// e[k] £ x.max, dla k= i, i+1, ..., (i+j)div 2 oraz
		// x.min £ e[k] , dla k= i, i+1, ..., (i+j)div 2 (założenie)
	y := min_max3 (e, (i+j)div 2+1, j);	// e[k] £ y.max, dla k= (i+j)div 2, ..., j-1, j oraz
		// y.min £ e[k], dla k= (i+j)div 2, ..., j-1, j (założenie)
	if (x.min £ y.min) then
	result.min := x.min
	else	// result.min £ e[k], dla k= i, ..., j
	result.min := y.min fi;
	if (y.max £ x.max) then result.max := x.max
	else	//e[k] £ result.max , dla k= i, ..., j
	result.max := y.max fi;
	fi
}		// result.min £ e[k], e[k] £ result.max dla k=i, ..., j

Zanim przejdziemy do analizy poprawności, prześledźmy na przykładzie, jak działa ten algorytm. Omawiany algorytm jest rekurencyjny, tzn. w jego treści będziemy się ponownie do niego odwoływać. Rozważmy ciąg o 16 elementach. Wartości tych elementów nie są teraz istotne. Zanotujmy tylko parametry kolejnych wywołań. Zapiszemy je w postaci grafu (por. Rys. 3.1). Każde wywołanie, o ile dotyczy ciągu o więcej niż dwóch elementach, spowoduje dwukrotne wywołanie funkcji min_max3. W rozważanym przykładzie pierwsze wywołanie ma parametry (1,16). Ponieważ ciąg ma więcej niż dwa elementy, zatem zostaną wykonane instrukcje po "else", tzn. wywołamy dwukrotnie funkcję min_max3 z parametrami (1,8) i (9,16). Wywołanie min_max3 dla ciągu 8 elementowego znów spowoduje dwa rekurencyjne wywołania funkcji z parametrami (1,4) i (5,8) itd. Pierwsze porównanie zostanie wykonane dopiero, gdy rozważany fragment ciągu ma dwa elementy.

Pytanie 3: W jakiej kolejności będą zakończone wywołania rekurencyjne funkcji min_max3 dla n=8?

Udowodnimy, że jeżeli przed wywołaniem funkcji min_max3(e,i,j) spełniony jest warunek a(i,j) = {j-i+1 = 2^k dla k>0}, to po wykonaniu algorytmu spełniony jest warunek b(i,j) = {result.min = min(e[i],...,e[j]), result.max = max(e[i],...,e[j]}.

Dowód poprawności algorytmu min_max3 zaczniemy od przypadku, gdy j-i=1 tzn. ciąg składa się tylko z dwóch elementów. W takim przypadku zostanie wykonana instrukcja warunkowa:

Po jej wykonaniu result.min jest elementem najmniejszym we fragmencie ciągu od e[i] do e[j] , a result.max jest elementem największym, co oznacza, że algorytm działa poprawnie dla ciągów dwuelementowych.

Załóżmy, że algorytm działa poprawnie dla wszystkich ciągów o długości 2^(k-1),gdzie k>1, i rozważmy ciąg dwa razy dłuższy j-i+1=2^k . Zgodnie z treścią algorytmu, wykonujemy dwa wywołania funkcji min_max3. Ponieważ (i+j)div 2 - i+1 = j - (i+j)div 2 = 2^(k-1), zatem na mocy założenia indukcyjnego, po wykonaniu wywołań

x.min £ e[l] £ x.max dla l = i, i+1, ..., (i+j)div2 oraz y.min £ e[l] £ y.max dla l = (i+j)div2 +1, ..., j.

Mniejsza z wartości x.min i y.min jest, na mocy przechodniości relacji £, niewiększa od e[i], e[i+1],..., e[(i+j)div2] oraz e[(i+j)div2+1], e[(i+j)div2+2], ..., e[j], czyli jest najmniejszym elementem ciągu e[i],...,e[j]. Większa z wartości x.max i y.max jest elementem największym ciągu e[i],...,e[j]. Zatem po wykonaniu instrukcji warunkowej, rozważane wywołanie funkcji min_max3 zakończy się i spełniony będzie warunek

Wykazaliśmy w ten sposób, że algorytm działa poprawnie dla ciągów o długości 2^k. Na mocy zasady indukcji matematycznej, jeżeli dane spełniają warunek {j-i+1 = 2^k dla k>0}, to po wykonaniu min_max3(e,i,j) otrzymane wyniki spełniają warunek b(i,j) dla dowolnej liczby naturalnej k>0. W szczególności, gdy n jest potęgą dwójki, wykonanie min_max(e,1,n) daje, dla dowolnego ciągu e, wyniki spełniające warunek końcowy specyfikacji algorytmu.

Twierdzenie 3.1 Dla dowolnych danych spełniających warunek wp = {($k)(n = 2^k)}, w dowolnej strukturze, która ma określony liniowy porządek elementów, algorytm rekurencyjny min_max3 zatrzymuje się, a otrzymany wynik spełnia warunek końcowy

wk ={result.min = min(e), result.max= max(e)}.

Niech T(n) oznacza koszt wykonania (mierzony liczbą wykonanych porównań) algorytmu min_max3 dla danych o rozmiarze n i niech n= 2^k. Jeśli ciąg ma tylko dwa elementy, to algorytm wykonuje jedno porównanie w celu ustalenia, który z elementów jest większy. Jeśli ciąg ma więcej niż dwa elementy, to dzielimy go na dwie części i dwukrotnie wywołujemy funkcję min_max3. Na koniec wykonujemy dodatkowo 2 porównania by ustalić wartość elementu najmniejszego i największego. Korzystając z przyjętego oznaczenia możemy zdefiniować funkcję T rekurencyjnie:

Rozwiązaniem tego równania rekurencyjnego jest funkcja T(2^k) = 3 ´ 2^(k-1) -2.

Rzeczywiście dla k=1, T(2) = 3´2⁰ - 2 = 3 - 2 = 1, co jest zgodne z definicją funkcji T(n). Załóżmy, że T(2ⁱ)= 3 ´ 2^(i-1) - 2 dla pewnego i. Udowodnimy prawdziwość wzoru dla i+. Korzystając kolejno z definicji rekurencyjnej i z założenia indukcyjnego otrzymujemy

T(2ⁱ⁺¹) = 2´T(2ⁱ) + 2 = 2´(3 ´ 2^(i-1) -2) + 2 = 3 ´ 2ⁱ - 2,
co należało udowodnić.

Ostatecznie, T(n) = 3n/2 - 2 dla wszystkich liczb naturalnych n, będących potęgą 2.

Wadą omawianej tu metody jest użycie rekursji, co jest zawsze związane z koniecznością zapamiętywania parametrów kolejnych wywołań. Zwykle tworzy się do tego celu stos. To oczywiście zajmuje czas i wymaga dodatkowego miejsca. W następnym punkcie omówimy wersję iteracyjną tego algorytmu.

Pytanie 4: Ile razy zostanie wywołana funkcja min_max3, jeśli w pierwszym wywołaniu parametrem aktualnym funkcji jest ciąg 128 elementowy oraz i = 1, j = 128?