Python recursion and exceptions

Inspiration

When I tried to get a list from a tree data structure represented as list of lists I had to realize that I cannot find a solution for my problem. (Maybe or probably because I am not as good at google search as this task requires…)

Anyway during the work to create a solution I came across some questions. For example, how to decide what is a list and what is not? Should I use generators? If I used generators how can I fuse generators in generators? Is there other way than recursion? Etc.

So this short article is just a little part of the knowledge I have gained on this learning path.

Flattening a tree data structure

What is wrong with it? Nothing :)
Except there is no official implementation of it. (As far as I know.)

So what can a simple program writer do? Write one.

So I wrote my first version, but during the process I had to face lots of considerations regarding readability and compactness.

I ended up with a simple recursive program snippet with a try-except block in the center. It is implemented as a generator function, what can improve your code in in many points of view.

Problems with it:

• Maybe recursion is not a friend of Python, as the number of recursive calls has an upper limit. ( You can query or even set this limit via [sys.getrecursionlimit] but be careful when changing its value!) Personally, I like recursion even though it can be slower and can consume more memory than the solution theoretically requires.

Of course in case of python, because [it doesn’t support tail recursion]. What is tail recursion in a few words. A kind of recursive call makes possible for the running program to free up memory thus your program will perform better.
(I would recommend to read about tail recursion and functional / logical programming style if those terms are not familiar to you.)

• Exception is the other question here. Some programming languages implement it in a usable way some not but python just did it right, but it comes with need of computation resource.

As many before me asked and have been answered, thus I must quote the/an answer from the Python design FAQ:

A try/except block is extremely efficient if no exceptions are raised. Actually catching an exception is expensive.

[exception performance]

What does it mean, exactly? The try-except code without exception raised is faster than a simple if statement.
So it is good if you almost never have exceptions. BUT if it is known that you will get a ton of exceptions you should avoid this solution because it will blast your code performance.
(as you will see in a later post)

Conclusion:

I like this code snippet, for the code readability concept in mind. It’s short, readable… but unfortunately it doesn’t perform well :(

In numbers with the same test set:

• faltten function (14–17s) is the worst if you want to use in a loop but if you want to use the advantages of generator it returns right away :D
• flatten3 (8–10s) performs better (python 3.4 interpreter)
• flattenpp (7–8s) this is a point when we drop the exceptions and use hasattr instead. Well, it performed better but expected more actually. Also the generator concept used in the worst case.
• flatteni (6–7s) it also recursive, but left the concepts of exception and generator. I didn’t track the memory usage but I am sure this one is the worst in that point of view.

I used this code snippet to test solutions:

As you can see I tried other solutions as well provided by Python itself, but those solutions work only with a 2D-array data structure. Only my solution works on tree data structures.

I have to highlight the first to solution for 2D-array. They are amazingly fast! First one uses itertools module what is very useful in many cases. The second one uses Python: List Comprehension