Non-recursive solution for recursive problem | developer.brewmp.com Non-recursive solution for recursive problem | developer.brewmp.com

Developer

Non-recursive solution for recursive problem

Forums:

Hi!

I have a PC game that uses recursive call to find adjancenct cells,
but I can't use it in BREW, due to stack limitations.

Imagine a chess board, with some random pieces on it.
If the user clicks on a cell, I must visit every cell that is connected
to it, and so on...

How do you deal with this?

from my generic programming experience, usually recursion can be flattened with a stack (here the word "stack" is a term of data structure to describe the "last in first out" storage order. it has nothing to do with brew's 4K stack for local vars and function calls etc).
for example, in your program you can create a stack to store "cells to be visited". when a cell is clicked, it is pushed to the stack. then, every time you pop a cell from stack and analyze it. the adjacent cells of the cell being analyzed are pushed to the stack too. keep this going. when the stack is empty you finished the analyzing.
in brew, the above "cells to be visited" stack can be a data structure allocated in heap. so you avoid to use the limited 4K system stack.
the above is the general idea.

from my generic programming experience, usually recursion can be flattened with a stack (here the word "stack" is a term of data structure to describe the "last in first out" storage order. it has nothing to do with brew's 4K stack for local vars and function calls etc).
for example, in your program you can create a stack to store "cells to be visited". when a cell is clicked, it is pushed to the stack. then, every time you pop a cell from stack and analyze it. the adjacent cells of the cell being analyzed are pushed to the stack too. keep this going. when the stack is empty you finished the analyzing.
in brew, the above "cells to be visited" stack can be a data structure allocated in heap. so you avoid to use the limited 4K system stack.
the above is the general idea.

Example:
int Recursive_Str_Len(char *str) {
int len = 0;
if (*str) len = 1 + Recursive_Str_Len(++str);
return len;

int NonRecusive_Str_Len(char * str){
int len = 0;
while (*str) { len += 1; p++; }
return len;

All recursion algorithm can be made as linear using while(), for() or do ... while(). It is a math law. You can use auxiliar matrixes or data to help on loop control.
If, only if, you must use recursion avoid at all cost to pass any parameter but pointers or atomic types (int, char, etc). Otherwise, depending on the number of interactions in the recursion you may overflow the stack... such as recursion over matrixes are n*n order!
[]'s

Example:
int Recursive_Str_Len(char *str) {
int len = 0;
if (*str) len = 1 + Recursive_Str_Len(++str);
return len;

int NonRecusive_Str_Len(char * str){
int len = 0;
while (*str) { len += 1; p++; }
return len;

All recursion algorithm can be made as linear using while(), for() or do ... while(). It is a math law. You can use auxiliar matrixes or data to help on loop control.
If, only if, you must use recursion avoid at all cost to pass any parameter but pointers or atomic types (int, char, etc). Otherwise, depending on the number of interactions in the recursion you may overflow the stack... such as recursion over matrixes are n*n order!
[]'s

I think if you try do to a few examples in hand of the recursive function with small cases you can get the idea of how the recursive algorithm works as a non recursive and implement with the stack in the heap instead of in the real stack.
i did this when my teacher asked me to print the nodes of a tree in "pre-order" in a non recursive manner, as the recursive is trivial. :)

I think if you try do to a few examples in hand of the recursive function with small cases you can get the idea of how the recursive algorithm works as a non recursive and implement with the stack in the heap instead of in the real stack.
i did this when my teacher asked me to print the nodes of a tree in "pre-order" in a non recursive manner, as the recursive is trivial. :)

btw, for each visit of your tree node, you should ISHELL_SetTimer() with 0 ms..
only if your tree is not too deep at you´re sure that this is not going to take long at any case in any phone you don´t need to do this...but I guess if you have a very small tree like this you wouldn´t have to code your own stack..

btw, for each visit of your tree node, you should ISHELL_SetTimer() with 0 ms..
only if your tree is not too deep at you´re sure that this is not going to take long at any case in any phone you don´t need to do this...but I guess if you have a very small tree like this you wouldn´t have to code your own stack..

FYI, ISHELL_Resume() is less expensive than ISHELL_SetTimer(0), as the app can preallocate a single AEECallback structure, while BREW has to do that for every timer call.

FYI, ISHELL_Resume() is less expensive than ISHELL_SetTimer(0), as the app can preallocate a single AEECallback structure, while BREW has to do that for every timer call.

Josemarin,
In our last game, we had a recursive problem which sounds very similar if not identical to yours. Most board and or puzzle games share a recursive problem. I used a recursive solution which passed no arguments and had no local variables. I calculated the maximum amount of recursive calls that could occur and took into account the stack space already depleted before the initial recursive call. My worst case scenario is about 450 bytes of stack space, that includes everything. Each of my recursive call requires a tiny space of the stack, so a pre-existing fragmented memory condition would not affect me either. As posted previously, there are other solutions, but a recursive one is possible.
-Mickey Portilla

Josemarin,
In our last game, we had a recursive problem which sounds very similar if not identical to yours. Most board and or puzzle games share a recursive problem. I used a recursive solution which passed no arguments and had no local variables. I calculated the maximum amount of recursive calls that could occur and took into account the stack space already depleted before the initial recursive call. My worst case scenario is about 450 bytes of stack space, that includes everything. Each of my recursive call requires a tiny space of the stack, so a pre-existing fragmented memory condition would not affect me either. As posted previously, there are other solutions, but a recursive one is possible.
-Mickey Portilla

use tailrecursion :cool:

use tailrecursion :cool:

There is ALWAYS a way of coding a recursion into a iterative form.. You can, in the worst case, alloc a big array to store the arguments and use an index into it..
/kUfa

There is ALWAYS a way of coding a recursion into a iterative form.. You can, in the worst case, alloc a big array to store the arguments and use an index into it..
/kUfa

Hi, Mickey Portilla
How do you calc the stack space?
I read in the Brew docs that I can't use global or static variables,
but I can do this:?
////////////////////////////////////////////////////////////
static CMyApp* MyApp;
void RecursiveFunction(){
// Do something...
if(MyApp->SomeCondition)
RecursiveFunction();
}
static void MyApp_HandleEvent(CMyApp *pMe, ...){
//... some events
MyApp = pMe;
RecursiveFunction();
}
////////////////////////////////////////////////////////////
The point is: may I use static variables values, inside one only call of HandleEvent?
PS: Maybe this is a little confuse....

Hi, Mickey Portilla
How do you calc the stack space?
I read in the Brew docs that I can't use global or static variables,
but I can do this:?
////////////////////////////////////////////////////////////
static CMyApp* MyApp;
void RecursiveFunction(){
// Do something...
if(MyApp->SomeCondition)
RecursiveFunction();
}
static void MyApp_HandleEvent(CMyApp *pMe, ...){
//... some events
MyApp = pMe;
RecursiveFunction();
}
////////////////////////////////////////////////////////////
The point is: may I use static variables values, inside one only call of HandleEvent?
PS: Maybe this is a little confuse....

JoseMarin,
There are probably good primers on system and or user stacks on the net, you should do some googling and read one.
First find out how much stack space the device you are targetting has. You can get this information from the data specifications in the extranet. Then assume all stack space is avaliable at the entry point into your prgram. BREW may have used some stack space up before getting to your program, but it is probably minimal. Without doing a lot of work, you can guess a magic number and subtract that from the stack space. I would say no more than 100 bytes, I would hope less but I have not confirmed the exact amount. Maybe someone from the BREW team can post this quantity for us. From your entry point start adding up the stack space you use up. This includes four bytes (possibly 2 bytes if compiling for thumb) for any function call. Function arguments, local variables and return values go on the stack. In my recursive solution, I had no arguments, no local variables and no return value. The algorithm uses class members, which are on the heap, to perform all of its functionality. If you you are coding in c, then you'll have to pass in the app struct pointer, another four bytes (again, possibly two if thumb). Keep in mind that you can't figure how much stack space is used by BREW functions. Maybe a future version of the BREW API document will list funtion stack space requirements (ahem, along with other technical information that is currently missing). Keeping track of stack space is crucial in embedded programming, regardless of recursive solutions. Blowing the stack on an embedded device is probably the worse error that can occur. Always use a safety margin when figuring out your space requirements.
-Mickey Portilla

JoseMarin,
There are probably good primers on system and or user stacks on the net, you should do some googling and read one.
First find out how much stack space the device you are targetting has. You can get this information from the data specifications in the extranet. Then assume all stack space is avaliable at the entry point into your prgram. BREW may have used some stack space up before getting to your program, but it is probably minimal. Without doing a lot of work, you can guess a magic number and subtract that from the stack space. I would say no more than 100 bytes, I would hope less but I have not confirmed the exact amount. Maybe someone from the BREW team can post this quantity for us. From your entry point start adding up the stack space you use up. This includes four bytes (possibly 2 bytes if compiling for thumb) for any function call. Function arguments, local variables and return values go on the stack. In my recursive solution, I had no arguments, no local variables and no return value. The algorithm uses class members, which are on the heap, to perform all of its functionality. If you you are coding in c, then you'll have to pass in the app struct pointer, another four bytes (again, possibly two if thumb). Keep in mind that you can't figure how much stack space is used by BREW functions. Maybe a future version of the BREW API document will list funtion stack space requirements (ahem, along with other technical information that is currently missing). Keeping track of stack space is crucial in embedded programming, regardless of recursive solutions. Blowing the stack on an embedded device is probably the worse error that can occur. Always use a safety margin when figuring out your space requirements.
-Mickey Portilla

google the net for "dynamic programming"
http://www.google.com/search?&q=dynamic%20programming
I was taught this in school as a method to solve most recursive problems interativly ( although i never really got the hang of it ). Might be worth reading about.

google the net for "dynamic programming"
http://www.google.com/search?&q=dynamic%20programming
I was taught this in school as a method to solve most recursive problems interativly ( although i never really got the hang of it ). Might be worth reading about.