Czy "czujesz" rekurencję?

Proponuję małe wyzwanie dla sprawdzenia samego siebie. Zachęcam do podjęcia się go i nie korzystania z Google'i do odkrycia rozwiązań. Zadanie to ma swoje źródło w książce "Structure and Implementation of Computer Programs", jednak - żeby nie straszyć publiczności ;) - przedstawię je w C++, nie w Scheme. Poniższy kawałek kodu oblicza funkcję Ackermanna:
int ackermann(int x, int y)
{
	if(y == 0)
	{
		return 0;
	}
	if(x == 0)
	{
		return 2*y;
	}
	if(y == 1)
	{
		return 2;
	}
	return ackermann(x-1, ackermann(x, y-1));
}
Zadanie na rozgrzewkę: jaką wartość przyjmą poniższe wyrażenia?
ackermann(1, 10);
ackermann(2, 4);
ackermann(3, 3);
Prawdziwe wyzwanie: rozważmy poniższe funkcje:
int f(int n)
{
	return ackermann(0, n);
}
int g(int n)
{
	return ackermann(1, n);
}
int h(int n)
{
	return ackermann(2, n);
}
int k(int n)
{
	return 5*n*n;
}
Jaką matematyczną definicję posiadają powyższe funkcje? Na przykład, funkcję k(n) można zdefiniować jako: k(n) = 5n2. Do rozwiązywania powyższych zadań nie trzeba nic kompilować - wystarczy kartka papieru i trochę cierpliwości :). Kompilator może się przydać do sprawdzenia wyników. Życzę powodzenia!