1

Can every recursive function be rewritten using tail calls? If not, what are examples of recursive functions for which this can't be done?

MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
  • 5
    tl;dr If you're willing to add an extra parameter explicitly representing the calling context, then yes. – pigworker May 11 '13 at 08:38
  • 1
    ... but of course that frequently means more than O(1) auxiliary space cost. –  May 11 '13 at 08:53
  • 2
    The calling context has to be represented somehow, somewhere, just as it is before the transformation. There's also a danger that transformation into tail-recursive form obscures opportunities for parallelism. – pigworker May 11 '13 at 09:13

0 Answers0