View unanswered posts | View active topics It is currently Thu Apr 24, 2014 7:01 am






Reply to topic  [ 9 posts ] 
Recursion 
Author Message
Expert

Joined: Sun Aug 19, 2007 2:43 pm
Posts: 134
Location: New Jersey
Post Recursion
Before i dive into writing something more elaborated with recursion, I thought I should test it with something REALLY simple like factorial to observer memory usage when things got pushed onto the stack.. I thought I could use the nAvailFlash or kSystemNxtAvailFlash. But, they keep saying 0 or 66 respectively.

Advice?


Sun Jan 27, 2013 10:04 pm
Profile WWW
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1347
Post Re: Recursion
Hmm, I know that RobotC didn't support recursion before because it didn't support stack. But I am not sure if that's still true for the latest RobotC after they have revamped to 3.x. It shouldn't be too hard to write a small test to check that out though.


Mon Jan 28, 2013 3:20 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3116
Location: Rotterdam, The Netherlands
Post Re: Recursion
3.5x supports recursion. I used it in one of my tutorials: http://botbench.com/blog/2013/01/20/tut ... in-robotc/

I don't know what the stack size is, I recall about 256 bytes per task with a max recursion depth of about 20. Don't pin me on that, though.

= Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Mon Jan 28, 2013 4:52 am
Profile WWW
Expert

Joined: Sun Aug 19, 2007 2:43 pm
Posts: 134
Location: New Jersey
Post Re: Recursion
MHTS wrote:
It shouldn't be too hard to write a small test to check that out though.


that's why I wrote the factorial recursion... that is as simple as it can get for recursion test. My question was how do I tell the stack size with robotC? You said it should not be too hard.. What would you suggest?


Mon Jan 28, 2013 1:34 pm
Profile WWW
Expert

Joined: Sun Aug 19, 2007 2:43 pm
Posts: 134
Location: New Jersey
Post Re: Recursion
mightor wrote:
I don't know what the stack size is, I recall about 256 bytes per task with a max recursion depth of about 20. Don't pin me on that, though.

= Xander


Thank you for the info... wonder if Timothy F. may verify this for us!? Better yet, is it a way to find out? I thought I could use nAvailFlash or kSystemNxtAvailFlash, but they do not seem to reflect the usage.

My students wrote a DFS simulation using iteration in RobotC. Pain in the neck to say the least. They wrote the NQueen and Huffman Coding w/ MS Visual C.... they all work beautifully. But, now we are curious to see if it is doable in RobotC. Not that we want to port nqueen and huffman coding, but to rewrite the dfs with recursion instead. So, before I even suggest to them to rewrite it in recursion, I hate to have them shoot in the dark and spend time on it but come to find out it is not doable. In order to minimize the stack size, their structure is extremely compact already... almost no bits are wasted. However, to be able to monitor the stack size will be greatly helpful.


Mon Jan 28, 2013 1:45 pm
Profile WWW
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1347
Post Re: Recursion
elizabeth.mabrey wrote:
MHTS wrote:
It shouldn't be too hard to write a small test to check that out though.


that's why I wrote the factorial recursion... that is as simple as it can get for recursion test. My question was how do I tell the stack size with robotC? You said it should not be too hard.. What would you suggest?

I am assuming if the stack is overflowing, it will throw an exception and terminate your program. If that's the case, you can get an idea of how big the stack is by slowly increasing the N of your N-factorial program. The stack use of your program is proportional to the depth of the recursion and the depth of the recursion is determined by N.


Mon Jan 28, 2013 1:58 pm
Profile
Guru
User avatar

Joined: Sun Nov 15, 2009 5:46 am
Posts: 1347
Post Re: Recursion
elizabeth.mabrey wrote:
My students wrote a DFS simulation using iteration in RobotC. Pain in the neck to say the least. They wrote the NQueen and Huffman Coding w/ MS Visual C.... they all work beautifully. But, now we are curious to see if it is doable in RobotC. Not that we want to port nqueen and huffman coding, but to rewrite the dfs with recursion instead. So, before I even suggest to them to rewrite it in recursion, I hate to have them shoot in the dark and spend time on it but come to find out it is not doable. In order to minimize the stack size, their structure is extremely compact already... almost no bits are wasted. However, to be able to monitor the stack size will be greatly helpful.

Are your students in high school? Those are pretty advanced for high school students. BTW, what is DFS? Distributed File System? Sorry, I am an OS guy. That's what comes to mind. Probably not since I can't imagine why one would write a file system on the Mindstorms.


Mon Jan 28, 2013 2:15 pm
Profile
Novice

Joined: Sun Oct 21, 2012 10:01 pm
Posts: 76
Post Re: Recursion
Depth-first search (makes an awesome maze solver!)? http://en.wikipedia.org/wiki/Depth-first_search


Mon Jan 28, 2013 3:14 pm
Profile
Moderator
Moderator
User avatar

Joined: Tue Sep 14, 2010 9:19 pm
Posts: 496
Post Re: Recursion
I wrote DFS and Dijkstra's in ROBOTC, just as an exercise, and it was quite tedious without recursion.

_________________
sudo rm -rf /


Mon Jan 28, 2013 4:27 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 9 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.