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.
The tests are there but it ain't free. Cost is...