[taos-glug] Re: stack frames

So, here is how this works in "real life" in Scheme vs, say, C or Perl.

Consider this pseudo-code:

i=0
while( i < 10)
      i = i + 1

this could also be written as shown below (assuming I did not make a 
typo).  This is called "tail recursion".

func(j){
  if(j >= 10) return j
  return func( j+1 )
}
func(0)

As Jon noted, this function need not build the stack for the seemingly 
recursive call to func.  Unfortunately, most languages do.  They do not 
know how to optimize this away.  A recent discussion on perlmonks.org 
leads me to believe that perl does not do the optimization.  [As an 
aside, it would be interesting to see if GCC can do the optimization, 
especially given RMS' interest in Lisp...]  Lisp-derived languages 
generally (always?) *do* perform the optimization. This is why one often 
sees tail recursion in these languages and why the base languages do not 
generally contain the more traditional looping constructs.

I once observed a C course where tail recursion was presented before 
while loops and while loops were explained in terms of tail recursion. 
The instructor strongly believed that tail recursion was more natural 
than loops.  Personally, it is for some things, but not always.  In my 
mind computing factorials is the classic example of when tail recursion 
is appropriate.

Personally I think it is important to understand why the various 
languages choose the syntax and semantics they do.  What I want is 
computer languages to make it easier for me to express to the computer 
what is in my head.  Sometimes I have to compromise for speed (e.g. 
choose C instead of perl for some tasks), but in general it is the 
expression that counts.

When I first learned lisp in college I could not find a use for it.  I 
still have never written a real application in lisp/Scheme/Guile.  The 
ideas, however, do help to fill one's toolbox when writing in other 
languages like perl, C or Ruby.

--john

Jonathan Bartlett wrote:
> One problem w/ SICP is that it makes more assumptions about the reader
> than it should.
> 
> That said, there is a pretty easy way to know if something is truly
> recursive or not.
> 
> The reason you need to build up stack frames is NOT to call a function,
> but to come back and finish a function.  For example, if I have a program:
> 
> sub foo()
> {
> int a, b
> 
> a = 3
> b = 2
> 
> return multiply(a, b);
> }
> 



-- 
John McDermott
Writer, Educator, Consultant
jjm@xxxxxxxxxx          http://www.jkintl.com
V +1 505/377-6293 F +1 505/377-6313

Other related posts: