recursion limit

General discussions and questions abound development of code with MicroPython that is not hardware specific.
Target audience: MicroPython Users.
gratefulfrog
Posts: 147
Joined: Sun Mar 01, 2015 12:10 pm

recursion limit

Post by gratefulfrog » Tue Jun 14, 2016 5:27 pm

Hi,

I just ran into the recursion limit in micropython on the pyboard...

Is there any way of adjusting that limit , eg. sys.setrecursionlimit ?

or even accessing it, eg. sys.getrecursionlimit()

Thanks,
Bob

pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Re: recursion limit

Post by pfalcon » Wed Jun 15, 2016 11:55 am

No, recursion limit is based on the actual system stack limit, it's not possible to adjust it at runtime on such a low-memory system. However, you might be able to patch MicroPython source code to use another (static) limit - at your own risk, and you will need to spend a lot of time to test that you didn't break anything (and then if you face any issue in the future, the suspicion will always be on your tricking with the stack, i.e. you will need to resolve all issues on your own).

None of that is likely needed however - the usual reason to hit recursion limit is doing something wrong. So, it's better to reconsider what you do, and how, to avoid it.
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

gratefulfrog
Posts: 147
Joined: Sun Mar 01, 2015 12:10 pm

Re: recursion limit

Post by gratefulfrog » Wed Jun 15, 2016 11:58 am

Thanks for that.

Sadly, I am a lisp programmer and often use recursion. There as nothing wrong with the code which runs fine on micropython on linux, and if I reduce the depth by changing the data it works fine as well.

In the meantime, I re-wrote it all as iterative, so it's ugly but works ;-)

Thanks for your help!
Ciao,
B

pfalcon
Posts: 1155
Joined: Fri Feb 28, 2014 2:05 pm

Re: recursion limit

Post by pfalcon » Wed Jun 15, 2016 12:30 pm

Sadly, I am a lisp programmer and often use recursion.
Really? Good to know.

Well, MicroPython is intended/optimized for standard imperative Python style. There's no tail call optimization, and we optimize for more rare heap usage at the expense of higher stack usage, which puts addition limit on recursion depth.

So, rewriting algorithm to work in iterative fashion (and e.g. maintain worklist-style stack on heap) is the way to go. There's also an experimental "stackless MicroPython" which vice-versa optimizes stack usage by using heap for everything possible (including Python functions stack), but I doubt that idea to use heavily recursive algorithms on deeply embedded systems is to good. Feel free to play with it though.
Awesome MicroPython list
Pycopy - A better MicroPython https://github.com/pfalcon/micropython
MicroPython standard library for all ports and forks - https://github.com/pfalcon/micropython-lib
More up to date docs - http://pycopy.readthedocs.io/

gratefulfrog
Posts: 147
Joined: Sun Mar 01, 2015 12:10 pm

Re: recursion limit

Post by gratefulfrog » Wed Jun 15, 2016 12:36 pm

I know that there is no tail optimization, but for parsing, I always think recursively. In my current application the expressions are at most 16 characters long, so I am hoping that 16-deep calls will make it somehow, if not, I will re-write...

actually, what I meant to say is: I am a lisp programmer and *ALWAYS* use recursion...

To iterate is human, to recurse, divine...

Also well said in The Eternal Flame ;-)

User avatar
patvdleer
Posts: 46
Joined: Mon Jun 13, 2016 11:52 am
Location: Maastricht, NL, Europe
Contact:

Re: recursion limit

Post by patvdleer » Thu Jun 16, 2016 8:19 pm

You've sparked my curiosity, did you run into a stack overflow? and if so, how? The only actual Lisp I every used was what ReSharper made refactored from what I wrote in C#.
NodeMCU v0.9 / V1 / V2 / V3
WeMos D1 Mini
WeMos Lolin32 v1.0.0
WeMos Lolin D32 Pro V2

gratefulfrog
Posts: 147
Joined: Sun Mar 01, 2015 12:10 pm

Re: recursion limit

Post by gratefulfrog » Thu Jun 16, 2016 8:55 pm

In may application, I have to read files from disk and load them into the program.

On disk, they are written in human friendly format. In the application, it is all structured data in classes. So, I have to parse.

Parsing is an intrinsically recursive activity. I am using a modal parsing strategy, to read the files. I would have used the python csv module if it were available in micropython. Anyway, in my first version there was a recursive call for every character in the line, some lines are about 140 characters long. That was too many calls for the small stack on the pyboard, although it ran fine on micropython on Linux.

Since it was all written tail recursively, it was easy to rewrite as iteration.

That's the whole story ;-)

Let me know if you want more details or anything else! I am a long time lisper. This is a lisp literate program I wrote years ago to do stock market analysis for a friend. Actually, it could be used for many things, it's more of a framework, or an inference engine framework. Check it out: SAL.

Ciao,
Bob

User avatar
patvdleer
Posts: 46
Joined: Mon Jun 13, 2016 11:52 am
Location: Maastricht, NL, Europe
Contact:

Re: recursion limit

Post by patvdleer » Thu Jun 16, 2016 9:07 pm

Well two question come to mind; Why are you doing that on the PyBoard? and; "every character in the line" why not a for loop? treat the string as an array of characters.

P.s. Thanks! pdf downloaded and added to calibre!
NodeMCU v0.9 / V1 / V2 / V3
WeMos D1 Mini
WeMos Lolin32 v1.0.0
WeMos Lolin D32 Pro V2

gratefulfrog
Posts: 147
Joined: Sun Mar 01, 2015 12:10 pm

Re: recursion limit

Post by gratefulfrog » Thu Jun 16, 2016 9:14 pm

I'm building a circuit for an electric guitar, it needs to read/write data to files on the sd card.

I know that "normal" people do things in loops, but the rest of us recurse.

Please don't take offense, but if you want to see how programming can be poetic, check out the Wizard Book. If you can get into it, it will change your way of thinking for ever, and for the better.

Here this link to the SICP, and if you prefer videos, here's 20 hours of videos which make up the bulk of the book, (the book is better!) If you decide to read it, I strongly recommend doing every exercise, until you get it right! It's worth it!

As to adding that doc to a public sharing site... maybe you should at least read it first to see if it is of interest to anyone ;-)

User avatar
patvdleer
Posts: 46
Joined: Mon Jun 13, 2016 11:52 am
Location: Maastricht, NL, Europe
Contact:

Re: recursion limit

Post by patvdleer » Thu Jun 16, 2016 9:29 pm

I will definitely look into SICP!

Calibre is an ebook manager not a public sharing site ;) I.e. let's me manage my books on my ereader.

B.t.w. the pdf link said .be, I'm guessing you are from Belgium? I'm officially Dutch but since I'm from Maastricht most of the Netherlands would say I'm Belgium too.
NodeMCU v0.9 / V1 / V2 / V3
WeMos D1 Mini
WeMos Lolin32 v1.0.0
WeMos Lolin D32 Pro V2

Post Reply