proper tail calls

Graydon Hoare graydon at
Mon Jan 21 10:53:32 PST 2008

Igor Bukanov wrote:

> I am saying that even for calls in the tail position an implementation
> may not eliminate the parent frame completely as it still may be
> exposed via closures. As such the tail call optimization cannot
> guarantee that the space complexity of the tail recursion is O(1).

This is much like saying "if the function in the tail call appends a 
value to an array, it is not O(1)". We're talking about stack growth, 
not side-effects on escaped heap objects. They have indefinite lifetime 
anyways. Who's to say the storage is even freed when g() runs and nulls 
out f2?


More information about the Es4-discuss mailing list