Max recursion

Discussion related to "under the hood" OpenMV topics.
s1000rr
Posts: 10
Joined: Wed Jan 31, 2018 12:33 am

Max recursion

Postby s1000rr » Sun Feb 04, 2018 1:57 pm

Hi,

Been running some tests and I occasionally get a pop saying "Maximum recursion depth exceeded" or sometimes just "ded" in the serial terminal. Is this a memory issue or is there a max number of recursions?

Thanks
User avatar
kwagyeman
Posts: 2198
Joined: Sun May 24, 2015 2:10 pm

Re: Max recursion

Postby kwagyeman » Sun Feb 04, 2018 2:22 pm

You're running code on a microcontroller. You shouldn't have any code that re-curses in general. If you need to do something recursive then you may wish to use a list to keep track of what you are up to.

A memory inefficient way to do this is to just store context using object state on a list.

E.g.

Code: Select all

init_state = (some, tuple, of, arguments)
list = [init_state]

# breadth first search

while(len(list)):
  new_state = list.pop(0)
  
  # do stuff
  
  list.append((next_state))
  list.append((another_next_state))
  etc.

# depth first search

while(len(list)):
  new_state = list.pop()
  
  # do stuff
  
  list.append((next_state))
  list.append((another_next_state))
  etc.

Or, for a more efficiently you can pre-allocate an array wish you manage as a list and once the maximum depth on that is exceeded you stop. The memory inefficient way is quick and dirty and will get you what you need by can't handle as much depth as the memory efficient way (about 1/2 less).

Anyway, we have a lot more heap than stack (50 KB versus 4 KB). So, the above should be find as long as the list doesn't get too long and you're not storing that many variables per state. Also, when the stack overflows that is undetectable... but, a heap overflow is and we can recover.

...

How many levels are in your recursion?
Nyamekye,
s1000rr
Posts: 10
Joined: Wed Jan 31, 2018 12:33 am

Re: Max recursion

Postby s1000rr » Sun Feb 04, 2018 3:27 pm

I'm not sure how deep it would go, it would depend on the image but I'd guess 2-3 recursions with each level having 1-4 elements calling a recursion. I wasn't aware that recursions should not be run on a microcontroller, thank you for letting me know this and for your alternate implementation suggestions. I will try both the methods you suggested.

Will there be a performance difference between the two other than memory?

Thanks
User avatar
kwagyeman
Posts: 2198
Joined: Sun May 24, 2015 2:10 pm

Re: Max recursion

Postby kwagyeman » Sun Feb 04, 2018 3:58 pm

Do the simple one first, and if you think you need more performance then switch.
Nyamekye,

Return to “Technical Discussion”

Who is online

Users browsing this forum: No registered users and 7 guests