/*
Napisati rekurzivnu funkciju koja racuna stepen broja i izracunati slozenost
*/

/*
koristimo:
x^n = x^(n-1) * x
x^0 = 1 
*/
int stepen1(int x, int n)
{
	if (n==0) return 1;
	else return x*stepen1(x, n-1);
}
/*
T(n) = T(n-1) + 1, pa je T(n) = O(n) (pogledati resenje sa predavanja)
*/

/*
koristimo:
x^n = x^(n/2) * x^(n/2) za n parno
x^n = x^(n/2) * x^(n/2) * x za n neparno
x^0 = 1
*/
int stepen2(int x, int n)
{
	if (n==0) return 1;
	else if (n%2) return stepen2(x, n/2)*stepen2(x,n/2)*x;
		else  return stepen2(x, n/2)*stepen2(x,n/2);
}
/*
T(n) = 2T(n/2) + c, pa je T(n) = O(n) (pogledati teoremu sa predavanja)
*/

//poboljsana verzija prethodnog
int stepen3(int x, int n)
{
	int pom;
	
	if (n==0) return 1;
	else 
	{
		pom = stepen3(x,n/2);
		if (n%2) return pom*pom*x;
		else return pom*pom;
	}
}
/*
T(n) = T(n/2) + c, pa je T(n) = O(log n) (pogledati teoremu sa predavanja)
*/

#include <stdio.h>

int main()
{
	int x, n;
	
	printf("Uneti broj i stepen");
	scanf("%d%d", &x, &n);
	
	printf("Stepen broja na prvi nacin je %d\n", stepen1(x, n));
	printf("Stepen broja na drugi nacin je %d\n", stepen2(x, n));
	printf("Stepen broja na treci nacin je %d\n", stepen3(x, n));
}