Как использовать цикл для завершения рекурсивной функции?

Question

Я пытаюсь написать программу, которая использует цикл для рекурсивной процедуры вместо использования условных выражений. Как я могу предотвратить бесконечные бесконечные вызовы, используя цикл в качестве "прерывания"?

Я понимаю, что цикл автоматически использует ecx в качестве счетчика, и когда ecx равен 0, цикл прекращается, однако моя программа, кажется, работает бесконечно из-за рекурсивных вызовов в цикле.Я также попытался с инструкцией jmp и поместил цикл в другое место несколько раз, и у меня все еще есть программа, работающая бесконечно.

.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

Ожидаемый вывод - 10 0 1 2 3 4 5 6 7 8 9 (печатается 0 - 9, потому что рекурсивная процедура должна выполняться 10 раз, 10 - userVal), однако я получаю 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14... (работает бесконечно)

Answer 1

... написать программу, которая использует loop для рекурсивной процедуры вместо использования условных выражений ...

Я считаю это интересной задачей, потому что она требуетнестандартного мышления.Он, вероятно, не имеет практического применения, но, тем не менее, имеет некоторые достоинства, подтверждающие концепцию.

Инструкция loop кодируется с 8-разрядным смещением со знаком, что означает, что условный переход может перейти назад и вперед !В большинстве (если не во всех) случаях, когда loop все еще используется сегодня, мы бы только прыгнули назад.
Помещение инструкции loop сверху выглядит очень неестественно, но работает нормально.

Нижекод работает в 2 этапа

• подготовительный этап помещает в стек набор адресов возврата (рекурсивные вызовы)
• производительный этап выводит все эти адреса возврата и печатает текущий номер

Помещение inc count перед call WriteInt выставленным call WriteInt как хвостовой вызов , и поэтому я могу заменить его на jmp WriteInt.
Когда начальная фаза начинается, ECX будет 0. Поэтому вместо использования переменной count в памяти я использовал для этой цели регистр ECX.
Код защищен от вводабесконечный цикл и провоцирующее переполнение стека с помощью инструкции jecxz Done.

    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:

Интересно, что написать это так же просто, используя loop обычным способом, поэтому прыгать назад.Однако он требует дополнительного приращения на счетчике, и он прыгает намного больше (см. Сравнение ниже).

    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:

Ниже я сравнил оба метода.Я удалил вызовы на WriteInt по понятным причинам ...

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

Фрагмент слева выполнен за 282 мкс, фрагмент справа - за 314 мкс.Это на 11% медленнее.