How to use a Loop to terminate a recursive function?

Question

I am trying to write a program that uses a loop for a recursive procedure instead of using conditionals, how do I prevent the calls running infinitely using a loop as the "break"?

I understand that the loop will automatically use the ecx as the counter and when ecx is 0, the loop will terminate, however, my program seems to run infinitely due to the recursive calls within the loop. I also tried with the jmp instruction and positioned the loop elsewhere multiple times and I still have the program running indefinitely.

.data
count DWORD ?     ;the counter for the # of times the loop ran
userVal DWORD ?    ;the # of times the loop will run according to the user

.code
    main PROC

        mov count, 0

    call ReadDec          ;read userinput for userVal, and stores it in ecx as counter
        mov userVal, eax
        mov ecx, userVal 
        mov eax,0

        call recur       ;call the recursion procedure
        ;call DumpRegs   ;for showing registers
        exit

    main ENDP 

    recur PROC USES ecx eax       ;the recursion Proc(objective: terminate the procedure with decrementing ecx 
                                  ; so the recursion will run ecx # of times) 

        mov eax, count                ;store  the count (starts with 0)
        call WriteInt                 ;prints the count in consol
        inc count     ;increment count everytime recursion is called    

        L2:     ;the loop

        call recur ; recursive call

        loop L2
    ret
    recur ENDP

END main

The expected output is 10 0 1 2 3 4 5 6 7 8 9 (0 through 9 is printed because the recursive procedure should run 10 times, 10 is the userVal), However, I am getting 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14...(running infinitely)

Answer 1

... write a program that uses a loop for a recursive procedure instead of using conditionals ...

I find this an interesting challenge because it requires some out-of-the-box thinking. It has probably zero practical use but has nonetheless some proof-of-concept merits.

The loop instruction is encoded with a signed 8-bit displacement, which means that the conditional jump can jump backward and forward! In most (if not all) cases where loop is still used today we would only jump backward.
Putting the loop instruction on top, looks very unnatural but it works fine.

The below code works in 2 phases

• a preparatory phase pushes a bunch of return addresses on the stack (recursive calls)
• a productive phase pops all of those return addresses and prints the current number

Putting inc count before call WriteInt exposed call WriteInt as a tail call and so I could replace it with jmp WriteInt.
When the productive phase starts, ECX will be 0. Therefore instead of using a count variable in memory, I used the ECX register for this purpose.
The code is protected from entering an infinite loop and provoking stack overflow through the jecxz Done instruction.

    jmp     Start
; ----------------------
Recur:
    loop    .a          ; Jumps N-1 times
    jmp     .b          ; Jumps 1 time
.a: call    Recur
.b: mov     eax, ecx
    inc     ecx
    jmp     WriteInt    ; Returns N times
; ----------------------
Start:
    call    ReadDec     ; -> EAX (valid input is assumed)
    mov     ecx, eax    ; The unsigned number N is [0,4GB-1]
    jecxz   Done        ; In case N == 0
    call    Recur
Done:

Interestingly it is just as easy to write this using loop in the normal way, so jumping backward. It requires however an additional increment on the counter and it jumps around a lot more (See the comparison below).

    jmp     Start
; ----------------------
Recur:
    jmp     .b          ; Jumps N+1 times
.a: call    Recur
    mov     eax, ecx
    inc     ecx
    jmp     WriteInt    ; Returns N times
.b: loop    .a          ; Jumps N times
    ret                 ; Returns 1 time
; ----------------------
Start:
    call    ReadDec     ; -> EAX (valid input is assumed)
    mov     ecx, eax    ; The unsigned number N is [0,4GB-1]
    jecxz   Done        ; In case N == 0
    inc     ecx
    jz      Done        ; IN case N == 4GB-1 (stack overflow for sure!)
    call    Recur
Done:

Below is how I compared both methods. I removed the calls to WriteInt for obvious reasons ...

LOOP FORWARD                LOOP BACKWARD

    jmp     Start               jmp     Start
; ----------------------    ; ----------------------
Recur:                      Recur:
    loop    .a                  jmp     .b
    jmp     .b              .a: call    Recur
.a: call    Recur               mov     eax, ecx
.b: mov     eax, ecx            inc     ecx
    inc     ecx                 ret
    ret                     .b: loop    .a
                                ret
; ----------------------    ; ----------------------
Start:                      Start:
    mov     ecx, 25000          mov     ecx, 25000
    call    Recur               inc     ecx
                                call    Recur

The snippet on the left executed in 282 µsec, the snippet on the right did it in 314 µsec. That is 11% slower.