Iterative vs. Recursive coding
nagle at animats.com
Fri Aug 20 18:34:58 CEST 2010
On 8/20/2010 12:47 AM, News123 wrote:
> On 08/20/2010 02:26 AM, Steven D'Aprano wrote:
>> On Thu, 19 Aug 2010 22:00:16 +0000, Martin Gregorie wrote:
>>> Recursion can be quite a trick to get your mind round at first
>> Really? Do people actually find the *concept* of recursion to be tricky?
> Is this a sincere surprise or are you just boasting?
>> If I remember correctly, my puzzlement about recursion lasted about 15
>> seconds. I remember thinking "How does the function foo know that there
>> is a function foo when foo doesn't fully exist yet?", but once I accepted
>> the fact that it just does it all just seemed obvious. Getting recursion
>> *right* is sometimes tricky, but the idea itself isn't.
If you think about what the implementation has to do, it's quite
complicated. Which objects are copied, and which are merely
referenced? Is the recursion going to result in control being
inside the same object instance twice? Is the recursion a closure?
Is tail recursion possible, and does your language implement it?
Python does not do tail recursion, so using recursion
where iteration could do the job is generally a bad idea. Scheme, on
the other hand, always does tail recursion where possible.
Python does have generators, and I recently wrote a recursive
generator for a production application. I needed to descend a
specialized directory tree structure (the one used by the US
Securities and Exchange Commission to store filings) and
retrieve the last N days of filings. So I have a recursive
generator that returns directory after directory, descending
into the directories for years and quarters as necessary.
The calling function stops calling the generator when it
has found the information it needs, which happens before
the generator runs out. That's a real-life use case
for such a construct, and led to much shorter code than
a non-recursive implementation.
More information about the Python-list