🚀 go-pugleaf

In article <1992Apr06.025126.33552@slate.mines.colorado.edu>, jgore@Mines.Colorado.Edu (Jacob Gore) writes:
> Consider the following function for computing x to the power of n:
> 
> fun power(x,n) =
>   if n=0 then 1.0
>   else if n mod 2 = 1 then x * power(x,n-1)
>   else power(x*x, n div 2);
> 
> What is the likelihood of an SML implementation doing it in O(1) space?
> 
> Jacob
> --
> Jacob Gore			Mathematical and Computer Sciences
> <JGore@Mines.Colorado.Edu>	Colorado School of Mines
> 
> 	-- Member of the League for Programming Freedom --

If you transform this into a tail-recursive form, i.e.

        fun power(x,n) =
          auxpower(x,n,1.0);

        fun auxpower(x,n,res) =
          if n=0 then res
          else if n mod 2 = 1 then power(x,n-1,res*x)
          else power(x*x, n div 2,res);

then a good compiler should recognize that it is a tail-recursion, and
convert it into an iterative form, which would need constant space.

-- Marc Najork