Subject: RE: how to tail recurse From: "Frank A. Christoph" <christo@xxxxxxxxxxxxxxxxxx> Date: Thu, 23 Jul 1998 11:12:33 +0900 
Congratulations, you have just rediscovered continuationpassing style (CPS). In the general case, the "state" needed for the recursion is held temporarily in a closure which gets built up on the way down to the base case, and then invoked once on the way up. The closure is called a continuation, since it records "what happens after" you evaluate a term. (define (succ n) (+ 1 n)) (define (id x) x) (define (comp f g) (lambda (x) (f (g x)))) (define (depthcps node kont) (let ((par (parent node))) (if (nodelistempty? p) (kont 0) (depthcps par (comp kont succ))))) (define (depth node) (depthcps node id)) Your version is a specialization of depthcps, in exactly the same sense (incidentally) that a derived class is a specialization of a base class in an objectbased programming language. Continuations are mindbogglingly useful things that can be used to obtain iterative and, when they are firstclass objects, even concurrent behavior. You should be able to find a treatment of continuations and CPS in any good Scheme textbook or, indeed, any good textbook on functional languages, period. FC >In my first DSSSL project, I had the need for a function giving me the >depth of an element in the SGML structure. I had this depth function >defined thus: > >(define (depth node) > (let ((myparent (parent node))) > (if (nodelistempty? myparent) > 0 > (+ 1 (depth myparent))))) > >This is clearly not tail recursive since it does something to the >value returned by the recursive call. It occured to me that to make >it tail recursive, the solution was to carry the state forward as a >parameter of the recursive call. The result is this: > >(define (depthrecur node curdepth) > (let ((myparent (parent node))) > (if (nodelistempty? myparent) > curdepth > (depthrecur myparent (+ 1 curdepth))))) > >(define (depth node) > (depthrecur node 0)) > >The above can be taken as an illustration on how to transform a >nontailrecursive function into a tailrecursive one. I think the >key idea there is to "carry the state forward as a parameter of the >recursive call". DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread 


< Previous  Index  Next > 

Re: how to tail recurse, Toby Speight  Thread  FOTBuilder symbolBevel, Frank A. Christoph 
Re: how to tail recurse, Toby Speight  Date  FOTBuilder symbolBevel, Frank A. Christoph 
Month 