Ceasar's Mind

Follow me: @Ceasar_Bautista

Recursive Python Considered Harmful

with 11 comments

It somewhat recently occurred to me that recursion, despite it cleanliness, improves readability at a significant cost in memory. By piling on the stack trace, at best we get a function that uses O(n) memory, and quite possibly even one that is even worse. Given that any recursive function can be written using a while loop with O(1) memory bounds, recursion seems quite a poor choice for all practical purposes.

I brought this up at work and Alexey explained that while this is true, many (particularly, functional) compilers are intelligent enough to optimize the code for you if you use tail-recursion. Being unaware of the concept, I looked up how to convert a regular recursive function into a tail-recursive function and discovered I was wasting my time since Guido has decided not to implement tail-recursion in Python.

This begs the question then, is recursion ever useful in Python or should we go back to our code and start writing those while loops?

As I see it, there is only one reason to use recursion in Python and that is when you plan to memoize your function (which makes the function take up O(n) memory anyway). (Additionally, it may be helpful to write functions out as recursive functions in order to assist in proving things, but I think, again, the function would almost certainly need to be memoized or transformed.)

In all other cases, I believe while loops are the way to go. Besides the obvious problems with memory, there are a few other points worth mentioning.

For one, Python caps the stack height at 1000. While for some functions this may be okay, if you have any interest in scaling, this limit is way too small.

Additionally, function call overhead is Python is extremely slow. (Source: the official Python wiki.)

Anyway, that’s my two cents.

Advertisements

Written by Ceasar Bautista

2011/10/23 at 00:51

Posted in Uncategorized

Tagged with ,

11 Responses

Subscribe to comments with RSS.

  1. Some problems can’t be solved without using O(n) memory. Try, for example, getting the path from A to B in a graph. Regardless of whether or not you do it recursively, the memory usage must be O(|maximum acyclic path|), because you need to keep track of the path traversed so far.

    As to your second issue, about size being limited to 1000, it’s also true that many problems will never grow that big. I do think that this is a better point, though.

    Devin

    2011/10/23 at 04:53

  2. Devin stated a concrete example.

    Theoretically, any problem that requires more than O(n) memory, recursion will be no different from a while loop in terms of memory usage. As for all the overhead… they are just constants in the big O.

    Practically speaking, not everyone uses python for efficiency. Code up something concise and easy to understand beats everything else.

    Chao Xu

    2011/10/23 at 06:19

  3. In some cases O(n) really is O(log(n)), for example using recursion to traverse a tree is fine and recommended.

    xilun0

    2011/10/23 at 07:21

  4. Just to add another possible thought:

    Back in the ’70s it was understood that about 5% of a program will take up 95% of the total resources used. Therefore, in some ways it makes sense to just write code that looks nice, is readable and makes sense then use diagnostic tools to find the slowest parts and then just improve those parts (i.e. use recursion etc everywhere else).

    Froskoy

    2011/10/23 at 16:31

  5. All very good points that I’ll keep in mind. I think I may have hit Publish a little too quickly. (It was just somewhat upsetting to discover that there is no tail-recursion since I’ve run into problem with recursion quite a few times.)

    Ceasar Bautista

    2011/10/23 at 18:54

  6. Recursive algorithms often require only O(log n) steps. Consider bsearch: to search a sorted array of n=1024 sorted elements, it takes only log n =10 recursive calls (since each step halves the problem). So the recursion is not necessarily a poor choice, even without a tail-call optimization.

    Alexey Tourbin

    2011/11/18 at 23:05

    • Uhm, bsearch is not recursive. At least, I’ve never seen anyone implementing it recursively anyway…

      But I’m wondering about writing parsers and encoders. I guess I’ll just cross fingers and hope it doesn’t get to 1000 then (if it does get larger, we may have a security issue / DoS at our hands, anyway, in most of my cases).

      mirabilos

      2013/01/11 at 22:33

  7. Two things, like others said sensible recursive algorithms can be less than O(N) deep.
    Also it is not possible to write all recursive algorithms using a while loop and O(1) memory.
    I agreed that tail recursion is good, anyhow. Sadly C and python can’t do it.

    Sam

    2013/03/14 at 04:58

  8. Great blog here! Also your website lots up fast!
    What host are you the use of? Can I get your associate link to your host?
    I wish my site loaded up as quickly as yours lol

    dermawand reviews

    2013/08/06 at 07:06

  9. With one week left until Father¡¯s Morning, I¡¯m sure a lots of you are still scrambling to often search for the perfect gift to your dear old Dad. How about a incredibly snazzy watch? Citizen sent me among their latest Eco-Drive different watches – the CA0467-11H Eco-Drive Primo Chronograph Look at to be exact to experience. With a racing prompted design, this is a cool watch that could keep time and change heads. Let¡¯s take a nearer look. And of course this offers the ultra-convenient (plus eco-friendly) charging design that is certainly powered by light – any kind of light. It never requires a battery change and can charge in the sunshine, in the house, anywhere where there¡¯s ambient light. When fully charged, it will run for up to 6 months. Light is absorbed in the crystal and the dial the place that the solar cell converts the particular light to energy.
    [url=http://www.ekologistika.com/p-1373.html]http://www.ekologistika.com/p-1373.html[/url] 【送料無料】カシオ 腕時計 [CASIO] ジーショック [G-SHOCK] GD-110-1JF メンズ/ウォッチ 腕時計 #102675
    [url=http://www.ekologistika.com/p-1588.html]http://www.ekologistika.com/p-1588.html[/url] 【送料無料】カシオ 腕時計 [CASIO] オシアナス [OCEANUS] OCW-S100B-1AJF メンズ/腕時計 #107599
    Although the watch doesn¡¯t have an easy to see charging status indicator, when the reserve electrical power becomes too low, the 2nd hand will become moving in 2 second increments as an alternative to 1 second increments. This is an alert to show you it¡¯s time to orient the Primo to lead light. Placing the watch in the window sill on a new sunny day for 5-6 hours will fully charge the item. I wanted to begin with a little Gadgeteer trivia¡­ Fourteen rice, back in 1999, we posted a report on then brand new Citizen Eco-Drive watch. That review continues to create our yearly top 26 most read reviews even after all these years. That goes to exhibit that Citizen Watch Provider and Eco-Drive watches are in the same way popular as ever. It¡¯s easy to see why these watches are so popular. The new Primo watch is known for a sporty style that features a chunky stainless steel grey ion-plated case and also a clear mineral crystal. It has a 1/5 second chronograph measuring around 60 minutes, tachymeter, rotating 360 degree bezel and is particularly water resistant to 75 meters. http://www.ekologistika.com/

    seneSkara

    2013/11/27 at 23:29

  10. What’s Happening i am new to this, I stumbled upon this I’ve found It positively useful and it has aided me out loads.
    I hope to contribute & aid other users like its helped me.
    Great job.


Leave a Reply to mirabilos Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s