Subject: Tail recursion, was: processing character entities From: David Carlisle <davidc@xxxxxxxxx> Date: Wed, 28 Jul 1999 11:00:15 +0100 (BST) |
> A couple of simple examples would be very much > appreciated here David C. I see Brandon replied anyway, but perhaps a non lisp example ... The clasic functional programing example (whatever concept you are trying to show) is factorial. factorial(1) = 1 factorial(2) = 2 * 1 factorial(3) = 3 * 2 * 1 etc (it grows big, fast:-) Now the obvious recursive defintion of this factorial (n) = if n = 1 1 else n * factorial (n-1) However this is non tail recursive, when making the recursive call to evaluate factorial (n-1) the system has to stack up the state of all the local variables in the function (just n here) as it needs the current local value of n after the recursive call comes back. To rewrite this in a tail recursive manner, the standard trick is to introduce a supplementary function that builds up the value in the _arguments_ not in the recursion stack, like so factorial (n) = factorial_helper (n,1) factorial_helper (n,result) = if n =1 result else factorial_helper (n-1, n * result) This time round, the system knows that it does not need any of factorial_helper local information after it has made the recursive call, so it does not need to stack that information, and can treat the recursion as syntactic sugar for a loop. There is a formal theory you can apply to decide which functions may be written into tail recursive form (and you may even hope that an optimising compiler would rewrite that first `bad' form into the tail recursive form on its own). But basically you can't do it if there is essential use made of more than one recursive call, eg to do a depth first walk over a binary tree doing a recursive call to walk each branch, you can make one of the calls tail recursive, but the other is bound to use up recursion stack. David (Given the total lack of dsssl in this posting, probably best to stop this thread:-) DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: processing character entities, Brandon Ibach | Thread | Re: Tail recursion, was: processing, G. Ken Holman |
Re: Again with the System Identifie, Joerg Wittenberger | Date | substring comparison, Jany Quintard |
Month |