What function of $x$, $n$ is computed by this program?
Function what(x, n:integer): integer:
value : integer
value := 1
if n > 0 then
if n mod 2 =1 then
value := value * x;
value := value * what(x*x, n div 2);
what := value;
take what(2,8) U will get 256 as ans.
what(2,7) U will get 128 as ans.
Hence ans is xn.
But the beauty of this code is it is done in O(logn) time instead of O(n) time.