Subject: Re: Midfunction Recursion From: Erik Naggum <erik@naggum.no> Date: 23 Oct 2002 15:31:57 +0000 Newsgroups: comp.lang.lisp Message-ID: <3244375917435651@naggum.no> * Travis Whitton | While I don't have any problem understanding recursive functions where | the function call is the last statement in the function, this particular | function calls itself in the middle, and I can't rationalize exactly how | it works. Pardon me, but this made me laugh out loud. All that work by the Scheme freaks to teach people recursion and to abuse it for iteration, and the end result is that someone does not get it except for iteration! It had to happen. Nothing personal, Travis, this is your teachers' fault. | Can someone explain how calling uncompress inside of uncompress' let | statement works? Exactly like calling from somewhere else. But watch the arguments. The recursive call causes the tail to be processed before the head. This means that when you call (uncompress '((3 1) (2 0))), the first thing it does is compute (uncompress '((2 0))), which yields (0 0) by prepending a list of two 0's to the empty list. Then the rest of the first call takes control and prepends a list of three 1's to the tail it computed first, (0 0), and you get (1 1 1 0 0). The smart thing about this solution is that it avoids copying the list it has already constructed. That is indeed a good algorithm, but if one is concerned about wasted resources, reversing the list first does exactly the same good without the cost of the recursion. -- Erik Naggum, Oslo, Norway Act from reason, and failure makes you rethink and study harder. Act from faith, and failure makes you blame someone and push harder.