For an assignment in my assembly programming class, we were given the problem below. I tried to solve it a couple different ways, but I could only think of solutions that use conditional statements. I have not found an answer online or from others in the class. Coming from c++/javascript style languages I understand that there must be a base statement (otherwise the function could call itself forever). Would that not require a conditional statement?
Heres the problem:
**Direct recursion is a term used when a procedure calls itself. You do not want want to let a procedure keep calling itself forever, because the runtime stack would fill up. You need to limit the recursion in some way.
Write a MASM program that calls a recursive procedure. Label the procedure recProc. Inside this procedure, add 1 to a counter so you can verify the number of times it executes. Run your program with a debugger, and at the end of the program, check the counter’s value. Put a number in ECX that specifies the number of times you want to allow the recursion to continue.
Use only the LOOP instruction and no other other conditional statements.
Find a way for the recursive procedure to call itself a fixed number of times.
When using procedures, you need to ensure that registers and flags are preserved. You need to use PUSHFD/POPFD and PUSHAD/POPAD.**
loop is exactly like dec ecx / jnz (except for not modifying the status flags, weirdness with the address-size prefix, and being much slower on most CPUs).
Its branch displacement range is a standard rel8 [-128 .. +127], so there's no requirement that it be used for a backward branch.
Thus you can use it as a conditional without even jumping through any hoops, just use it to jump forward over the code for the recursion base-case (possibly just a ret):
; first arg in ECX = recursion count
my_func:
loop @keep_descending
;; fall-through path: ecx was 1 before loop, and is now 0
... do something here ...
ret
@keep_descending:
; ecx has been decremented by 1
push ebx ; save a call-preserved reg; use it to save state across the recursive call
... main body of function here ...
call my_func ; clobbers ecx; save it if needed
... more stuff
; If your function way was tail-recursive, you should have just made a loop
lea eax, [edx+ecx] ; return in EAX
pop ebx
ret
It's easy to abuse loop to use it as a generic if (n != 0) without modifying n, if your recursion termination condition is something other than a down-counter.
inc ecx ; 1 byte in 32-bit mode
loop ecx_was_non_zero
;; fall-through path: ecx was zero before inc, and is now zero again
This is 1 byte shorter than test ecx, ecx / jnz (in 32-bit mode), and thus useful for a code-golf GCD loop, where the only thing that matters is code-size, not performance. (An equivalent trick with CX works in 16-bit mode, but 64-bit mode doesn't have 1-byte inc.)
When using procedures, you need to ensure that registers and flags are preserved. You need to use PUSHFD/POPFD and PUSHAD/POPAD.
That's a crappy calling convention that imposes a lot of work on every function you call. It's totally normal to allow functions to clobber flags, and eax/ecx/edx, so they can use some registers without saving/restoring.
POPAD is really inconvenient to use, because it overwrites all the registers, including EAX where you wanted to put a return value. So you either have to save/restore EAX around the POPAD, or you have to store your result into the right spot on the stack for POPAD to load it into EAX.
Also, it's possible to leave registers and FLAGS unmodified without using pushad/popad, so that statement is false. Unless you take it as a separate requirement, also inconveniencing you the way the loop requirement does.
MASM is it possible to create a recursive function without conditional statement?
That's a different question (because loop is a conditional branch), but the answer still is yes. Your options include self-modifying code. (See The Story of Mel for an example.) In your case, you might have the start of the function overwrite the call instruction to a nop or something.
You can do that branchlessly with a cmov to get a pointer to either that instruction or some harmless location into a register. Or maybe you'd call cmov a conditional instruction. It's not a branch, but it has conditional in the name. Anyway, self-modifying-code is horrible for performance on modern CPUs, so you shouldn't use that either.
But if you're just coming up with silly computer tricks like abusing loop, then you should also consider self-modifying code, or a lookup table of pointers, or other ways of affecting flow control without a standard conditional instruction like jcc.