[PRL] almost tail-calling (was: Re: deeep stack)

[Joe Marshall]

It isn't just about the stack, though.  In a real program, each of
those frames is hanging
on to locals and arguments.  Depending on the program, this can make a
nasty change
in the order of space usage.  (See Clinger, Proper Tail Recursion and
Space Efficiency (1998))
He gives an example program that is O(n^2) in space if the language
isn't tail recursive,
but O(n) if it is.

No sane person would use Bubble sort (O (n^2) in time) when O(n log n)
solutions exist.
But people seem perfectly happy using a mechanism that can chew up
that much space.

On Thu, May 22, 2008 at 4:41 PM, John Clements
<clements at brinckerhoff.org> wrote:
> In teaching students last quarter, I had several of them "naively" implement
> methods recursively rather than using loops, and was surprised to discover
> how deep the stack could get without incident.  Just now, I decided to see
> how deep you could go (see *1* below), and I got to
>
> 518660
>
> That is, Java's not tail-calling, but that's not bad.  Now, these are itty
> bitty stack frames.  Adding another argument to the procedure pulls this
> down to 346000, and adding a third brings it down to 259000.
>
> Regardless, I would argue that it is _entirely_ reasonable to suggest that
> for the majority of real-world programming problems, students that use
> recursion instead of loops are justified if it saves them programming and/or
> debugging time; the latter is especially true since the stack traces will
> suddenly contain a whole bunch of useful information (and yes, I know that
> this is an argument _against_ tail calling).
>
> John Clements
>
>
> *1*
>
> class TestStackDepth {
>  static int testStackDepth(int i) {
>    if (i % 1000 == 0)
>      System.out.println (i);
>    return testStackDepth (i + 1);
>  }
>
>  public static void main(String args[]) {
>    testStackDepth (0);
>  }
> }
>
>
>
>
> On May 22, 2008, at 11:00 AM, Joe Marshall wrote:
>
>> I wonder how many of those frames are unnecessary (that is, simply
>> awaiting
>> a return in order to perform its own return)?
>>
>> On Wed, May 21, 2008 at 7:21 PM, Dave Herman <dherman at ccs.neu.edu> wrote:
>>>
>>> Challenge: how many layers of enterprise abstraction before you blow the
>>> Java stack? No recursion allowed, of course. :)
>>>
>>>
>>> http://ptrthomas.wordpress.com/2006/06/06/java-call-stack-from-http-upto-jdbc-as-a-picture/
>>>
>>> Dave
>>>
>>> _______________________________________________
>>> PRL mailing list
>>> PRL at lists.ccs.neu.edu
>>> https://lists.ccs.neu.edu/bin/listinfo/prl
>>>
>>
>>
>>
>> --
>> ~jrm
>>
>> _______________________________________________
>> PRL mailing list
>> PRL at lists.ccs.neu.edu
>> https://lists.ccs.neu.edu/bin/listinfo/prl
>
>



-- 
~jrm