Recursive functions

[Danesh]

Hi all,

Does anybody has any idea about recursive functions in assembly ? I need a clear template if you can. Also, I had always conern about stack overflow problems in VC and I did not use recursive functions as I could. Any idea to make sure that stack overflow will not occur if I use recursive in assemlby ?

Regards,

Danesh

[Eddy]

You can emulate the normal stack by building a stack of your own.
Reserve memory and write your own push and pop functions.
When your pseudo stack gets full, simply reserve more memory.

When your 'recursive' function calls itself:
- first store all the local variables of that function in your pseudo stack (by using your own push commands). Also store the return address. This is the address of the next line where you 'call' your recursive function.
- then reset all local variables
- then re-enter the recursive function by simply jumping (don't CALL !) to the beginning (or any convenient entry point) of that function.
- when the recursive function needs to be exited, recall the local variables of the previous recursion by popping them of your own pseudo stack. When there are no more variables stored on the stack, you must exit your 'recursive' function.
- then jump back to the address where your function called itself (the next address really) to continue.

It would be easier to explain with an example, but I'm afraid I haven't got any ..

Just emulate what happens when you really call a function recursively.
The advantage is that you now can dynamicaly increase your pseudo stack size so you never get a stack overflow.

Kind regards
Eddy

[sluggy]

I had this problem once when i wrote a function that could recurse into itself several hundred times. To prevent the stack overflow i just increased the size of the stack that the app was initially allocated, by using the .stack directive in my source, so it looked like this:

Code Select Expand


   .stack 4096


That number is in bytes, and the default for MASM is 1KB (which is 1024 bytes). So i increased it to 4 KB and never had a problem (i never did sit down and work out exactly how much stack space i needed, but any desktop should be able to afford 4KB).

[James Ladd]

Try looking up "tail cull" and you should find some text on how to avoid the stack issues.

[Eddy]

Do you mean "tail call" ?

Kind regards
Eddy

[James Ladd]

I mean "tail cull". As each time you recurse the tail of ret(s) is getting bigger and bigger.
You need some way to get rid of these. You cant actually get rid of them you have to
avoid them.

Essentially you need to avoid doing a call/ret

[Infro_X]

One thing you can do is overrighting your arguments on the stack and jump back to the beginning, but this only works if you don't use the original arguments after the jump (because they'll be corrupted).

[Eddy]

Essentially you need to avoid doing a call/ret

Correct. I tried to describe a method to achieve this in my first reply above.

Kind regards
Eddy

[gabor]

Hello!

I understand that in a recursion that runs several hundred times pushing the return addess can allocate stack space. But the parameters are allocating space too. So, eliminating the call/ret is just the half solution.
I would recommend 2 things:
- if it is worth (the size of the parameter to be passed is bigger than a dword) store the parameters in memory and pass a pointer to it. This work-around is mainly the same as creating your own stack as Eddy recommended.
- simply don't use recursion. Every recursion can be transformed into a traditional loop, and vica versa. Loop should be faster don't need big stack space but don't match the data structure and probably need other memory storage. Recursion is slower, needs more stack space, but can be created to match exactly the used data structure.

Other tip: allocate memory, create a "wrap" procedure for the recursion. This wrap procedure sets esp to this allocated space, makes the first recursion call, the recursion returns to this wrape proc, that restores esp...

Greets, Gábor

[hutch--]

There are two things being discussed here, iteration and recursion and while you can often replace recursion with iteration and see it go faster, if you need the variable preserved for each level of recursion, you cannot simply do that with iteration. A classic case of this is a quick sort where you leave existing information in each level of recursion while climbing up and down the tree. The data only becomes trashable when a recursion level is exited with a ret as the stack is then destroyed for that level.

It depends very much on what you need as to what you use, if you can rewrite a recursive algo as an iterative one without jumping through hoops, you often see a speed improvement as you save all of the stack overhead but some algos are piggishly hard to write as iterative when their original design is recursive.

[Danesh]

Thanks all. Unfortunately, I could not use any of tips from you until now, but about what hutch said. Actually, I am implementing a B-Tree inserting function and the algorithms is in recursive form in a book I found. B-Tree needs to be spiltted and working with them is very hard, has anybody any experience about B-Trees ?

Regards,

Danesh

[gabor]

Hi!

I learned about B trees, I would not say they algos are too comlicated. Splitting a B tree is not so difficult, believe me.
According to my uni book every method (insert, delete, search, min, max, interval) can be implemented with iterativ algos.
They are faster, though harder to follow or understand since they don't align to the structure of a tree.

I coded a recursive algo for DFS walking through a tree. Well, I know it can be realized with an iterativ algo, but this is hard. Here, the algo itself is recursive.

If you would appreciate some help with the B trees, I'd be ready to help.


Greets, Gábor

[Danesh]

Hi Gabor,

I am very impressed about new method (non-recursive) in implementing B-Trees. I am reading the book "Data structures & program design in C" by Robert Kruse/Tondo/Bruce Leung which is well known in B-Tree algorithms and it have used recursive methods to implement insert into a B-Tree. Actually, there is no other way because you have to keep track of each node when you are inserting a key into a leaf, because you might need the addresses of nodes you have visited to insert overloaded key and/or spilit any other node. I tried to implement a non-recursive method by adding a word to each node which points to its parent, but updating this node is very very deficcult and increases number of disk accesses which is far away of B-Tree goal to decrease number of disk accesses. So, I would appreciate your help first if you introduce the book you are using which has non-recursive implementation. I will ask you, if I have any question, but first would you please give me the name of your book ?

Regards,

Danesh

[gabor]

Hello Danesh!

I am sorry, this book was a university book we studied from. It is in hungarian. I suppose this is a "fatal error".  :bg
Are we really talking about the same data structure? Are you fully sure about that the insert cannot be implemented via iterativ methods?
Normally do you store pointers to the child nodes in a node?

I guess we could transform this topic into a B-tree topic, or open an other...
Then we could define the B-tree and its essential methods. And we could discuss efficient and optimal solutions of implementation.
If you are agreed, first briefly discribe what are the features of a B-tree (a definition like stuff).

Greets, Gábor

[Danesh]

Hi Gabor,

I have created a new topic with B-Trees title. I will explain briefly about B-Trees. If you have any idea about implementing B-Tree (Inserting and Deletion) algorithms in non-recursive form, please write there.

Yours,

Danesh