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

[John Clements]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2484 bytes
Desc: not available
Url : https://lists.ccs.neu.edu/pipermail/prl/attachments/20080522/bd0552be/attachment.bin