Does MATLAB perform tail call optimization?

Question

I've recently learned Haskell, and am trying to carry the pure functional style over to my other code when possible. An important aspect of this is treating all variables as immutable, i.e. constants. In order to do so, many computations that would be implemented using loops in an imperative style have to be performed using recursion, which typically incurs a memory penalty due to the allocation a new stack frame for each function call. In the special case of a tail call (where the return value of a called function is immediately returned to the callee's caller), however, this penalty can be bypassed by a process called tail call optimization (in one method, this can be done by essentially replacing a call with a jmp after setting up the stack properly). Does MATLAB perform TCO by default, or is there a way to tell it to?

Avoiding iteration just for the heck of it isn't a good idea. Use whatever is more apropriate to the given problem (and viable - of course iteration isn't practical in a purely functional language). — user395760
With proper tail-call optimization, "avoiding iteration" becomes a matter of how you think about the problem, not how your solution performs. If MATLAB doesn't offer TCO, then obviously I'll use iteration when I need to, but if it does I will be able to use a consistent paradigm across all of my code. — Shea Levy
I don't know any MATLAB in particukar, I'm speaking generally. If you were coding Python, and Python had TCO, you still shouldn't use recursion over loops, because it's not idiomatic, the language and stdlib are focused on getting the most out of iterators, etc. And regarding "consistent paradigm": Each paradigm has its weak points, so use whatever solve a given problem best (the definition of "best" also involves how well it works together with the rest, of course). — user395760
Y-Combinator in MATLAB: mathforum.org/kb/message.jspa?messageID=6636833&tstart=0 — Mikhail

Gareth McCaughan Gareth McCaughan · Accepted Answer · 2011-03-16T16:25:34

If I define a simple tail-recursive function:

function tailtest(n)
  if n==0; feature memstats; return; end
  tailtest(n-1);
end

and call it so that it will recurse quite deeply:

set(0,'RecursionLimit',10000);
tailtest(1000);

then it doesn't look as if stack frames are eating a lot of memory. However, if I make it recurse much deeper:

set(0,'RecursionLimit',10000);
tailtest(5000);

then (on my machine, today) MATLAB simply crashes: the process unceremoniously dies.

I don't think this is consistent with MATLAB doing any TCO; the case where a function tail-calls itself, only in one place, with no local variables other than a single argument, is just about as simple as anyone could hope for.

So: No, it appears that MATLAB does not do TCO at all, at least by default. I haven't (so far) looked for options that might enable it. I'd be surprised if there were any.

In cases where we don't blow out the stack, how much does recursion cost? See my comment to Bill Cheatham's answer: it looks like the time overhead is nontrivial but not insane.

... Except that Bill Cheatham deleted his answer after I left that comment. OK. So, I took a simple iterative implementation of the Fibonacci function and a simple tail-recursive one, doing essentially the same computation in both, and timed them both on fib(60). The recursive implementation took about 2.5 times longer to run than the iterative one. Of course the relative overhead will be smaller for functions that do more work than one addition and one subtraction per iteration.

(I also agree with delnan's sentiment: highly-recursive code of the sort that feels natural in Haskell is typically likely to be unidiomatic in MATLAB.)

Does MATLAB perform tail call optimization?

1 Answers