Tail recursion example.md

Consider the following two Standard ML functions for computing the sum of a list of integers:

fun nsum n =
    if n=0 then 0
           else n + nsum (n-1);

fun summing (n,total) =
    if n=0 then total
           else summing (n-1, n + total);

Using SmlToJs we can compile these two functions into the following JavaScript code:

if ((typeof(sum$2auto$0sum$1)) == "undefined") {sum$2auto$0sum$1 = {};
};
(function(){var fix$90 = {};
fix$90.$nsum = function(n$48){return (n$48 == 0)?0:(SmlPrims.chk_ovf_i32(n$48 + (fix$90.$nsum(SmlPrims.chk_ovf_i32(n$48 - 1)))));
};
sum$2auto$0sum$1.nsum$45 = fix$90.$nsum;
var fix$91 = {};
fix$91.$summing = function(v$62,v$63){lab$summing: while (true) {if (v$62 == 0) {return v$63;
} else {var t$92 = SmlPrims.chk_ovf_i32(v$62 - 1);
var t$93 = SmlPrims.chk_ovf_i32(v$62 + v$63);
var v$62 = t$92;
var v$63 = t$93;
continue lab$summing;
};
};
};
sum$2auto$0sum$1.summing$53 = fix$91.$summing;
return 0;
})();

Ignoring bounds checking and renaming variables, this is equivalent to the following code:

nsum = function (n) {
  return (n == 0) ? 0 : n + nsum(n - 1);
};

summing = function (m, n) {
  while (true) {
    if (m == 0) {
      return n;
    } else {
      r = m - 1;
      t = m + n;
      m = r;
      n = t;
    }
  }
};

Clearly nsum is still recursive while summing was compiled into a simple loop.

curiousleo/Tail recursion example.md