Recursion

[Bieb]

How does one go about implementing a recursive algorithm, like, say, quicksort, in asembly?

[cman]

If you use the high level syntax , the same way you would in a HLL :

myFunction proc param:DWORD

   
     .........
     invoke myFunction , 8

myFunction endp

otherwise use a call statement within the function. This is the same as your probably used to......

[hutch--]

Bieb,

There is a recursive quick sort in the current MASM32 library.

[Bieb]

So recursion isn't a contrivance of HLLs, but rather just something that works, even at the lowest levels?

[BogdanOntanu]

Yes recursion works in ASM as well as in any other languages ...
Actually it works better in ASM since you do not have to define the function first ...

[tenkey]

Recursion requires a stack. Your local variables must be on the stack, or else they won't act like local variables in HLLs.

While most processors these days will use a stack for a CALL instruction, there are many low performance processors that don't provide easy support for local variables. Some of these processors also have a return stack with a very limited size.

[hutch--]

Bieb,

Recursion is one of those useful designs when you need to hit the same code over and over again but it comes at a price and that is the use of stack memory. If the count of LOCAL variables in your proc is 16 bytes, for every additional call depth you have the CALL return address and the 16 bytes of LOCAL ariables and with very deep recursion you can go past the stack limit set in your executable file.

This is a common problem with a quick sort and one of the tricks with a quick sort is to limit the recursion depth and exit the complete procedure. Just as an example with the recently added string sorts in the MASM32 library, I made the choice of using a fully unprotected quick sort at the beginning of a sort design but if it collapses into excessive stack recursion, it exits and uses a different strategy to sort the strings.

As long as you have some mechanism in mind that limits the recursion depth, it is a very useful technique and is used for other things like climbing up and down a tree structure. Recursion is used with directory file searches because of the tree structure of directories.

[cman]

So recursion isn't a contrivance of HLLs, but rather just something that works, even at the lowest levels?

I think recursion is more of a way to use the system stack to save prior results and states than it is a characteristic of any programming language; kind of a way to put a "bookmark" in a proceedure and come back to it at a latter , more advantagous time. In LISP recusion is the primary control mechanism for repeating sequences of statements , replacing the iteration of most other languages ( but the compiler is written to eliminate the time/space penalties associated with recurrsive routines ); so if you like this method , you might try this language. Keep in mind that recursive routines can be written with a loop substituted for the recursive call ( I think I attemped to write quick sort without the final recursive call once ( very messy without the recursion , but perhaps more efficient ). I try to eliminate recursion as much as possible in my code , using it rarely and only when I get lazy enough.   :bg

[Robert Collins]

What would be the difference between a recursive function that acts upon the data from within as opposed to a function that returns its calculation and then recieves that same results as it's input parameter on successive calls from another point in the program where the calling code determines how many times to call the function? I see where speed could be an issue but anything else?

[MichaelW]

For a function called repeatedly from some other function, the parameters, return address, and local variables would be removed from the stack on return, restoring the state of the stack to what it was before the call. For a recursive procedure each recursion would place another copy of the return address and a new set of parameters and local variables on the stack, and these items would not be removed from the stack until all of the recursions had returned.

[Robert Collins]

For a function called repeatedly from some other function, the parameters, return address, and local variables would be removed from the stack on return, restoring the state of the stack to what it was before the call.

OK, suppose I call a function with an initial value of 10. The function does something with that value returning back to the caller the results, say 7. Now I call the function again passing to it the value 7. The function does the same calculations on that value returning back to me a value of 5. I call the function again passing it the value of 5. etc, etc until the returned value is say 1.

Why is this any different than a function doing a recursive action on the original value of 10 and at the end of the recursion return a value of 1?

[BogdanOntanu]

Because each time you call the recursive function you ARE ALREADY INSIDE the function you CALL :D
Are you able to see the difference?

So each time you RECURSE you go deeper and deeper into the STACK.

As Huch said before IF you have a lot of LOCAL variables then you will go deeper much faster faster, also at the end the returns will have to successively clear up all stack. Also the depth depends on DATA and not exactly on code so some data might crash your application while other data will work just fine, depends if you want such features in your application, beeing it HLL or not.

Recursion is usually slower that simple function calls, and it eats up much more memory on stack than anything else.
Normaly recursion should be avoided unless you are lazy or you want to use very simple solutions.

But there is fun in recursion and sometimes it is the most simple solution to problems ...

Still the kind of problems that recursion applys to are usually generated by "mind oriented" people ;)  and this kind of people have an inteligence that is very close to stupidity

So that is why recursion solves such problems (for example the tree structure of folders).

[Robert Collins]

For a function called repeatedly from some other function, the parameters, return address, and local variables would be removed from the stack on return, restoring the state of the stack to what it was before the call.

OK, suppose I call a function with an initial value of 10. The function does something with that value returning back to the caller the results, say 7. Now I call the function again passing to it the value 7. The function does the same calculations on that value returning back to me a value of 5. I call the function again passing it the value of 5. etc, etc until the returned value is say 1.

Why is this any different than a function doing a recursive action on the original value of 10 and at the end of the recursion return a value of 1?

Excuse me. I think I should have said..........

.......I call a non-recursive function with an initial value.......

and

......Why is this any different than a recursive function doing a recursive action on the original value.......

[Relvinian]

On of the most fun and learning ways what a recursive function does is to write the game:  Towers of Hanoi.

With that, you have fun learning recursing while also challenging yourself to see how well you can write that simple game.  ;-)

Relvinian

[MichaelW]

Robert,

The attachment is a quick-and-dirty program that I hope answers your question. Note that the recursive procedures will fault if passed a value of zero because the termination condition, an input value of 1, will never occur (before the program runs out of stack space).

[edit] Updated the attachment to correct a small problem[/edit]

[attachment deleted by admin]