Web form report: Trying to do recursion...

[mitappinv...@appinventor.mit.edu]

Date Submitted: Tue Feb 18 2014 03:51:05 GMT-0500 (EST)
Email: mar...@gmail.com

Service: MIT App Inventor (App Inventor 2)

Operating System: Windows Vista

Browser: Chrome

Device: emulator

Connection: USB Cable

Issue:
Trying to do recursion

Comments:
I'm trying to do recursion. (A procedure to call itself). However if the
procedure calls itself more than 300 times approximately the app stops. If
the procedure calls itself less than 300 times apporoximately the recursion
works correctly.
What happens?
Helping you: the project tries to fill a closed area with color and the
procedure fills a single pixel with color and calls itself to go to the
next pixel to do the same job. If the closed area has less than 300 pixel
everything is ok. If the closed area is bigger, there is a problem.
Can you help me?

[Enis]

I'll take a stab at this, but it's hard to tell without looking at your aia file.

It may be that the emulator itself has a memory leak someplace... the emulator isn't MIT's but Google's.

Could you be doing something that's overly using resources?

Perhaps you could either upload your AIA file, or at least post some screenshots of the blocks that are causing the issue...

[mitappinv...@appinventor.mit.edu]

[Taifun]

probably one of Scott's recursion examples can help?

https://groups.google.com/forum/#!searchin/app-inventor-developers-library/recursion

Taifun

[fturbak]

I absolutely adore recursion, and teach recursion before iteration in my intro programming classes (even in Java). 

However, a problem with recursion is that it can fail due to resource constraints if the recursion depth is too deep. Each recursive call requires memory for the procedure call frame, and the total memory space allocated for currently active procedure call frames is limited. This can vary from device to device, but I've typically seen App Inventor recursions fail between depths of 250 to 350 procedure call frames. Your reported failure at 300 calls is consistent with my experience. 

In cases like these, I'm afraid you have no choice but to rethink your algorithm, and try to recast it as an iteration rather than a recursion. 

- lyn -

[Abraham Getzler]

For a graphic fill operation, you might be better served by a clock-driven work queue,
using a list or two to track your frontier.

This would let you see your progress dynamically and avoid compute-hung time-outs.

You might try this algorithm...

Start with an empty queue of points.
Add your starting fill point to the queue.
Repeat this operation, driven by  fast clock:

• Pop a point off the queue.
• For each of the four compass directions off that point,
• Test how far you can fill in that direction from this point
• If it's more than 3 pixels long,
• Draw a line in that direction
• Add the midpoint of that line to the queue.

I'm attaching an old AI1 project to draw the Sierpinski Triangle using this work
queue technique.  Sorry, no write-up exists.

https://dl.dropboxusercontent.com/u/145520/Sierpinski.zip

ABG

On Tuesday, February 18, 2014 3:51:11 AM UTC-5, mitappinv...@appinventor.mit.edu wrote:

[Scott Ferguson]

We definitely need a good fill algorithm for AI.

In addition to Abraham's suggestion of using a queue, you also have the option of using a stack.

Let us know how it goes.

---

Scott