How would you optimally calculate p^k, where k is a non-negative integer? What is the complexity of the solution?

FUNCTION pow(base, exponent)
	IF exponent == 0
		RETURN 1
	ELSE IF exponent is even
		RETURN pow(base * base, exponent / 2)
	ELSE
		RETURN base * pow(base * base, (exponent - 1) / 2)
	END IF