> > > Thanks for the link. I wasn't clear enough about the problem I am trying > to solve. I want to duplicate the TokenOrderGenerator class in leoAst.py > without recursion or generators. > > I don't think it is possible what you are trying to achieve. To totally avoid any kind of recursion, you must know some facts about the AST in advance, for example how deep it is. If you were able to know this information, you could write an algorithm without any kind of recursion. But that would limit what AST your code can process. If you wish that your could can accept any valid Python code, then you have to use some kind of recursion, because your code would operate on the recursive data structure.
Now, there are two kinds of recursion. One is when a recursive function calls itself or two or more functions call each other recursively. This kind of recursion can reach Python limit for the number of recursive calls or it can fill the stack. The other kind of recursion is using generators. Calling a function which yields returns immediately, before the first iteration has started. This means that the stack space is not going to be exhausted, and instead all necessary data for executing recursion is going to be in the main memory and not on the stack. Python generators are the Pythonesque way of automatically transforming recursive code written in Python into the imperative code which is guaranteed to produce the same result as would the recursive one. This feature is implemented in C. Now, if you want to avoid using generators, theoretically you can transform recursive code which uses generators into the equivalent imperative code, but your implementation of such code written in Python must be much slower than the same code with generators. If you were able to write faster implementation in Python, that would mean that the C implementation of Python generators is not optimized, and that is highly unlikely because CPython source is pretty much optimized. You said earlier that Position class is not using recursion, but it isn't entirely true. The _stack field of the Position instances is where the recursion is hidden. One could say that by using _stack, Position class is just an implementation of the generators written in Python without using Python generators. This is the reason why I almost never use position methods for iteration and instead almost always write my own iterators using ordinary Python generators. In all my experiments and measurements using Python generators produced faster code than the equivalent code using position methods. It is O.K. if you just want to have some fun to play around with these ideas, but you should know that you can't avoid recursion because the data is recursive, and generators actually produce the fastest code for solving recursive problems in Python. It wouldn't be an easy task to get faster solution even in C, because Python C sources are already well optimized. My 2 cents. So, if you are looking to improve the speed, generators are your best choice. The graph theory literature may be vast, but it almost certainly does not > include this exact problem. Anyway, I'm having fun with the puzzle, even if > it may have been solved before :-) > > Edward > -- You received this message because you are subscribed to the Google Groups "leo-editor" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/leo-editor/d632d8bf-2b90-4721-89b8-2009061e7af3n%40googlegroups.com.
