Funkcja Ackermanna

Wstęp

Funkcja Ackermanna to rekurencyjna funkcja dwuargumentowa, której można użyć do sprawdzenia optymalizacji kompilatorów. Już dla bardzo małych argumentów wartość funkcji bardzo szybko rośnie.

Definicja

Funkcja Ackermanna przyjmuje dwa argumenty będące liczbami naturalnymi m i n. Jest ona określona przy pomocy wzoru rekurencyjnego przedstawionego poniżej:

\(A(m, n) = \left\{\begin{matrix}n+1 & m = 0\\ A(m-1,1) & m > 0, n = 0\\ A(m-1, A(m, n-1)) & m > 0, n > 0\end{matrix}\right.\)

Tabela wartości

Wartości funkcji można przedstawić w następującej tabelce:

Jak można zauważyć wartości dla stałego m rosną powoli według ustalonego wzoru, ale dla coraz większego m wartość funkcji jest coraz większa. Kolejny wiersz zawiera liczby za duże, aby przedstawić je w tabelce. Dla m = 4 kolejne liczby to: 13, 65533, 2⁶⁵⁵³⁶ - 3,.. Dla uświadomienia jak duża jest ostatnia wymieniona liczba dla A(4, 2) wystarczy sprawdzić ile by wymagała bitów do zapisu: 65536 bitów co jest równoważne 8192 bajtom czyli 8kB. Jak widać już dla bardzo małych m funkcja przyjmuje bardzo duże wartości.

Przykład

W celu obliczenia wartości A(2, 1) należy zgodnie ze wzorem rozpisać kolejno:
A(2, 1)
= A(1, A(2, 0))
= A(1, A(1, 1))
= A(1, A(0, A(1, 0)))
= A(1, A(0, A(0, 1)))
= A(1, A(0, 2))
= A(1, 3)
= A(0, A(1, 2))
= A(0, A(0, A(1, 1)))
= A(0, A(0, A(0, A(0, 0))))
= A(0, A(0, A(0, 1)))
= A(0, A(0, 2))
= A(0, 3) = 4.

Tutaj można zauważyć też kolejny problem zwiazany z obliczaniem wartości na komputerze. Funkcja nie tylko szybko rośnie, ale wymaga też odpowiednio dużo wywołań rekurencyjnych. Dla wartości wcześniej podanych w tabelce nie jest to problemem, ale dla A(4, 1) funkcja będzie wymagać 65533 wywołań rekurenycjnych zagnieżdżonych jedno w drugim. Większość kompilatorów nie dopuszcza ich tak dużo.

Implementacja

Zadanie polega na napisaniu funkcji, która dla podanych argumentów m i n. Użytkownik będzie mógł wprowadzić obydwie wymienione wartości, a następnie na konsoli zostanie wypisany wynik funkcji A(m, n).

Napisana funkcja Ackermann() składa się z dwóch warunków i w zależności od podanych parametrów zwróci odpowiednią wartość zgodnie ze wzorem. Ze względu na to, że funkcja może przyjmować bardzo duże wartości to zostanie zastosowany typ long.

1. long Ackermann(long m, long n) {
2.   if (m == 0)
3.     return n + 1;
4.   if (m > 0 && n == 0)
5.     return Ackermann(m - 1, 1);
6.   return Ackermann(m - 1, Ackermann(m, n - 1));
7. }

Testowanie funkcji

W celu przetestowania działania kodu poniższy fragment programu wczytuje od użytkownika argumenty, a następnie dla nich wypisuje wartość funkcji Ackermanna.

1. int main () {
2.   long n, m;
3.   cout << "Podaj argumenty\n n = ";
4.   cin >> n;
5.   cout << " m = ";
6.   cin >> m;
7.   long w = Ackermann(m, n);
8.   cout << "A(" << n << "," << m << ") = " << w;
9.   system("pause");
10.   return 0;
11. }

Uwaga: dla wartości m > 3 program może nie pomieścić wyliczonych wartości, albo zgłaszać wyjątek o przekroczeniu liczby dozwolnych wywołań rekurencyjnych.

• Kod źródłowy Implementacja