Timp estimat de citire: 12-13 minute
„Rutina care se cheamă pe ea însăși”
Varianta iterativă a căutării prin dihotomie — cea prezentată în capitol — folosește o buclă: ajustează limitele, recalculează mijlocul, repetă. E directă, economică, fără surprize.
Dar există și o altă cale, mai elegantă matematic: recursivitatea. În loc să ajustezi limitele și să te întorci la începutul buclei, rutină se cheamă pe ea însăși cu limite noi. Fiecare apel rezolvă o problemă mai mică, până când răspunsul e trivial: fie am găsit, fie spațiul s-a epuizat. E același algoritm, doar că în loc de o buclă care se învârte, ai o funcție care se oglindează în ea însăși.
În limbajele de nivel înalt, recursivitatea e simplă: compilatorul se ocupă de stivă, de salvarea contextului, de întoarcere. În Assembler, trebuie să faci tu tot. Și tocmai de asta e instructiv: vezi cu ochii cum fiecare apel recursiv depune pe stivă universul lui mic — registre, parametri, adresă de retur — și cum, la întoarcere, fiecare nivel își ridică universul înapoi, neatins.
MACRO-11: Recursivitate naturală
PDP-11 a fost creat parcă pentru recursivitate. Stiva hardware, cu auto-decrement la push și auto-increment la pop, face ca fiecare apel recursiv să fie doar o secvență de MOV-uri pe stivă urmată de JSR. La întoarcere, RTS PC restaurează totul automat.
Interfața: patru parametri pe stivă — adresa tabelei, cheia, limita inferioară (LOW) și limita superioară (HIGH). La primul apel, LOW e 1 și HIGH e N. Rezultatul se întoarce în R0: indexul găsit, sau 0 dacă nu există.
Cazul de bază: dacă LOW > HIGH, spațiul s-a epuizat, returnează 0. Altfel, calculează MID, compară, și se cheamă pe sine cu limite ajustate. Observați că adresa tabelei și cheia se retransmit identice la fiecare nivel — doar LOW și HIGH se schimbă.
Un detaliu PDP-11 care te poate înnebuni dacă nu știi: offset-urile de pe stivă sunt în octal. 10(SP) înseamnă octal 10, adică zecimal 8. 12(SP) e zecimal 10, 14(SP) e zecimal 12, și așa mai departe. Numărând în octal, stiva devine o hartă perfectă.
Apelul inițial:
; APEL INITIAL:
;
MOV N,-(SP) ; PUSH HIGH = N
MOV #1,-(SP) ; PUSH LOW = 1
MOV KEY,-(SP) ; PUSH KEY
MOV #TABLE,-(SP) ; PUSH TABLE ADDRESS
JSR PC,RBSRCH ; CALL
ADD #10,SP ; CLEAN STACK (4 PARAMS * 2 = 10 OCTAL)
; R0 = INDEX (1..N) OR 0
Rutina recursivă:
;=======================================================
; RECURSIVE BINARY SEARCH - MACRO-11 / PDP-11 / RT-11
;
; PARAMETERS ON STACK (PUSHED RIGHT TO LEFT):
; 2(SP) = TABLE ADDRESS (pointer to sorted word array)
; 4(SP) = KEY (search value)
; 6(SP) = LOW (lower bound, 1-based)
; 10(SP) = HIGH (upper bound, 1-based)
; (10 octal = 8 decimal)
;
; RETURNS: R0 = INDEX (1..N) IF FOUND, 0 IF NOT
;
; FIRST CALL:
; MOV HIGH,-(SP) ; push HIGH (=N)
; MOV LOW,-(SP) ; push LOW (=1)
; MOV KEY,-(SP) ; push KEY
; MOV #TABLE,-(SP) ; push TABLE address
; JSR PC,RBSRCH
; ADD #10,SP ; clean 4 params (octal 10 = 8)
; ; R0 = result
;=======================================================
RBSRCH: MOV R1,-(SP) ; SAVE REGISTERS
MOV R2,-(SP)
MOV R3,-(SP)
MOV R4,-(SP)
;
; LOAD PARAMETERS
; 4 saved regs + return addr = 5 words = 12 octal offset
;
MOV 12(SP),R1 ; R1 = TABLE ADDRESS
MOV 14(SP),R2 ; R2 = KEY
MOV 16(SP),R3 ; R3 = LOW
MOV 20(SP),R4 ; R4 = HIGH
;
; BASE CASE: LOW > HIGH? => NOT FOUND
;
CMP R3,R4 ; LOW > HIGH?
BGT RNFND ; YES: RETURN 0
;
; MID = (LOW + HIGH) / 2
;
MOV R3,R0 ; R0 = LOW
ADD R4,R0 ; R0 = LOW + HIGH
ASR R0 ; R0 = (LOW+HIGH)/2 = MID
;
; COMPUTE ADDRESS OF TABLE(MID)
;
MOV R0,-(SP) ; SAVE MID ON STACK
DEC R0 ; R0 = MID - 1
ASL R0 ; R0 = (MID-1) * 2 (WORD SIZE)
ADD R1,R0 ; R0 = ADDR OF TABLE(MID)
;
; COMPARE KEY WITH TABLE(MID)
;
CMP R2,(R0) ; KEY : TABLE(MID)
BLT RLEFT ; KEY < TABLE(MID)
BGT RRIGHT ; KEY > TABLE(MID)
;
; FOUND: RETURN MID
;
MOV (SP)+,R0 ; R0 = MID (POP)
BR RDONE
;
; KEY < TABLE(MID): RECURSE WITH HIGH = MID - 1
;
RLEFT: MOV (SP)+,R0 ; R0 = MID (POP)
DEC R0 ; R0 = MID - 1
;
; PUSH PARAMS FOR RECURSIVE CALL (RIGHT TO LEFT)
;
MOV R0,-(SP) ; PUSH NEW HIGH (MID-1)
MOV R3,-(SP) ; PUSH LOW (UNCHANGED)
MOV R2,-(SP) ; PUSH KEY
MOV R1,-(SP) ; PUSH TABLE ADDRESS
JSR PC,RBSRCH ; RECURSE!
ADD #10,SP ; CLEAN 4 PARAMS (OCTAL 10 = 8)
BR RDONE ; R0 = RESULT FROM RECURSION
;
; KEY > TABLE(MID): RECURSE WITH LOW = MID + 1
;
RRIGHT: MOV (SP)+,R0 ; R0 = MID (POP)
INC R0 ; R0 = MID + 1
;
; PUSH PARAMS FOR RECURSIVE CALL (RIGHT TO LEFT)
;
MOV R4,-(SP) ; PUSH HIGH (UNCHANGED)
MOV R0,-(SP) ; PUSH NEW LOW (MID+1)
MOV R2,-(SP) ; PUSH KEY
MOV R1,-(SP) ; PUSH TABLE ADDRESS
JSR PC,RBSRCH ; RECURSE!
ADD #10,SP ; CLEAN 4 PARAMS (OCTAL 10 = 8)
BR RDONE ; R0 = RESULT FROM RECURSION
;
; NOT FOUND: RETURN 0
;
RNFND: CLR R0
;
; RESTORE AND RETURN
;
RDONE: MOV (SP)+,R4 ; RESTORE REGISTERS
MOV (SP)+,R3
MOV (SP)+,R2
MOV (SP)+,R1
RTS PC ; RETURN (R0 = RESULT)
;
.END
ASSEMBLER IBM System/360: Recursivitate construită cu mâna
Pe /360, recursivitatea nu e imposibilă — dar nimeni nu ți-o oferă pe tavă. Nu există stivă hardware. Există Save Area — un bloc de 18 fullword-uri în care fiecare rutină își salvează registrele. Save Area-urile sunt înlănțuite: fiecare o pointează pe cea precedentă (înapoi) și pe cea următoare (înainte). E ca un lanț de vagoane, fiecare cu locul lui în convoi.
Problema: într-un apel normal, fiecare rutină are o singură Save Area, statică. Dacă rutina se cheamă pe sine, a doua invocare suprascrie Save Area primei — și la întoarcere, registrele sunt pierdute. Dezastru.
Soluția: o stivă simulată. Am pre-alocat o zonă de memorie (STACK) cu 20 de cadre a câte 96 de octeți fiecare — 18 fullword-uri pentru Save Area plus 6 fullword-uri pentru variabile locale și lista de parametri. Un pointer (STKPTR) ține evidența cadrului curent. La fiecare apel recursiv, pointer-ul avansează cu 96 de octeți; la întoarcere, reculează. 20 de niveluri sunt suficiente pentru 2 la puterea 20, adică peste un milion de elemente — mai mult decât încăpeau pe orice disc din 1972.
Instrucțiunea cheie este BALR R14,R15 — Branch And Link Register: salvează adresa de retur în R14 și sare la adresa din R15. E echivalentul lui JSR de pe PDP-11, doar că nu folosește stiva — folosește un registru. Tot restul — salvarea contextului, transmiterea parametrilor, restaurarea — se face manual, cu grijă și disciplină.
RBSRCH CSECT
*=============================================================
* RECURSIVE BINARY SEARCH - IBM SYSTEM/360
* OS/360 STANDARD LINKAGE WITH DYNAMIC SAVE AREAS
*
* PARAMETERS VIA R1 (STANDARD OS/360):
* +0 A(TABLE) - ADDRESS OF SORTED FULLWORD ARRAY
* +4 A(KEY) - ADDRESS OF FULLWORD: SEARCH KEY
* +8 A(LOW) - ADDRESS OF FULLWORD: LOWER BOUND
* +12 A(HIGH) - ADDRESS OF FULLWORD: UPPER BOUND
* +16 A(IPOS) - ADDRESS OF FULLWORD: RESULT INDEX
*
* RETURN CODE IN R15: 0=FOUND, 4=NOT FOUND
*
* NOTE: EACH RECURSIVE CALL USES A FRAME FROM STACK AREA.
* REGISTER R11 IS THE STACK POINTER, ADVANCING BY
* FRAME SIZE (96 BYTES) ON EACH CALL.
* MAX DEPTH = 20 (ENOUGH FOR 2^20 = 1M ELEMENTS)
*=============================================================
*
FSIZE EQU 96 FRAME SIZE (18F SAVE + 6F WORK)
*
*--- STANDARD ENTRY LINKAGE ---
*
STM R14,R12,12(R13) SAVE CALLER'S REGISTERS
LR R12,R15 ESTABLISH BASE REGISTER
USING RBSRCH,R12
*
*--- ALLOCATE FRAME FROM STACK ---
*
L R11,=A(STKPTR) R11 -> CURRENT STACK PTR
L R10,0(,R11) R10 = CURRENT FRAME ADDRESS
LA R9,FSIZE(,R10) R9 = NEXT FRAME ADDRESS
ST R9,0(,R11) ADVANCE STACK POINTER
*
*--- CHAIN SAVE AREAS ---
*
ST R13,4(,R10) BACKWARD CHAIN
ST R10,8(,R13) FORWARD CHAIN
LR R13,R10 R13 -> OUR FRAME
*
*--- LOAD PARAMETERS ---
*
L R2,0(,R1) R2 = A(TABLE)
L R3,4(,R1) R3 = A(KEY)
L R4,8(,R1) R4 = A(LOW)
L R5,12(,R1) R5 = A(HIGH)
L R6,16(,R1) R6 = A(IPOS)
LA R6,0(,R6) CLEAR HI BIT IF LAST PARM
*
L R7,0(,R3) R7 = KEY VALUE
L R8,0(,R4) R8 = LOW VALUE
L R9,0(,R5) R9 = HIGH VALUE
*
*--- BASE CASE: LOW > HIGH? ---
*
CR R8,R9 LOW > HIGH?
BH RNOTFND YES: NOT FOUND
*
*--- MID = (LOW + HIGH) / 2 ---
*
LR R10,R8 R10 = LOW
AR R10,R9 R10 = LOW + HIGH
SRA R10,1 R10 = MID
*
*--- COMPARE KEY WITH TABLE(MID) ---
*
LR R4,R10 R4 = MID
BCTR R4,0 R4 = MID - 1
SLA R4,2 R4 = (MID-1) * 4
C R7,0(R4,R2) KEY : TABLE(MID)
BL RLEFT KEY < TABLE(MID)
BH RRIGHT KEY > TABLE(MID)
*
*--- FOUND: IPOS = MID, RC = 0 ---
*
ST R10,0(,R6) IPOS = MID
SR R15,R15 RC = 0
B REXIT
*
*--- KEY < TABLE(MID): RECURSE(LOW, MID-1) ---
*
RLEFT LR R5,R10 R5 = MID
BCTR R5,0 R5 = MID - 1
ST R8,72(,R13) STORE LOW IN WORK AREA
ST R5,76(,R13) STORE NEW HIGH (MID-1)
*
* BUILD PARAMETER LIST IN WORK AREA
*
L R1,=A(SAVTBL) RELOAD A(TABLE) FROM SAVE
ST R1,80(,R13) PARM+0: A(TABLE)
L R1,=A(SAVKEY)
ST R1,84(,R13) PARM+4: A(KEY)
LA R1,72(,R13)
ST R1,88(,R13) PARM+8: A(LOW) -> WORK+0
LA R1,76(,R13)
ST R1,92(,R13) PARM+12: A(HIGH) -> WORK+4
*
* NOTE: IPOS ADDRESS STAYS IN R6, PASSED THROUGH
*
B RCALL
*
*--- KEY > TABLE(MID): RECURSE(MID+1, HIGH) ---
*
RRIGHT LA R5,1(,R10) R5 = MID + 1
ST R5,72(,R13) STORE NEW LOW (MID+1)
ST R9,76(,R13) STORE HIGH (UNCHANGED)
*
L R1,=A(SAVTBL)
ST R1,80(,R13) PARM+0: A(TABLE)
L R1,=A(SAVKEY)
ST R1,84(,R13) PARM+4: A(KEY)
LA R1,72(,R13)
ST R1,88(,R13) PARM+8: A(LOW) -> WORK+0
LA R1,76(,R13)
ST R1,92(,R13) PARM+12: A(HIGH) -> WORK+4
*
*--- COMMON RECURSIVE CALL ---
*
RCALL LA R1,80(,R13) R1 -> PARAMETER LIST
* SET LAST PARM INDICATOR
L R5,92(,R13) LOAD LAST PARM ADDR
O R5,=X'80000000' SET HI BIT
ST R5,92(,R13) STORE BACK
*
L R15,=A(RBSRCH) R15 = ENTRY POINT
BALR R14,R15 CALL SELF (RECURSE!)
* R15 = RETURN CODE FROM RECURSIVE CALL
B REXIT
*
*--- NOT FOUND: IPOS = 0, RC = 4 ---
*
RNOTFND SR R10,R10
ST R10,0(,R6) IPOS = 0
LA R15,4 RC = 4
*
*--- STANDARD EXIT: DEALLOCATE FRAME ---
*
REXIT L R11,=A(STKPTR) RESTORE STACK POINTER
L R10,0(,R11)
S R10,=F'96' POP ONE FRAME
ST R10,0(,R11)
*
L R13,4(,R13) RESTORE CALLER'S R13
L R14,12(,R13) RESTORE R14
LM R0,R12,20(R13) RESTORE R0-R12
BR R14 RETURN
*
*--- CONSTANTS AND WORK AREAS ---
*
SAVTBL DS A SAVED A(TABLE) FOR RECURSION
SAVKEY DS A SAVED A(KEY) FOR RECURSION
STKPTR DC A(STACK) CURRENT STACK POINTER
STACK DS 20CL96 STACK: 20 FRAMES * 96 BYTES
* (MAX DEPTH 20 = 2**20 ELEMS)
*
R0 EQU 0
R1 EQU 1
R2 EQU 2
R3 EQU 3
R4 EQU 4
R5 EQU 5
R6 EQU 6
R7 EQU 7
R8 EQU 8
R9 EQU 9
R10 EQU 10
R11 EQU 11
R12 EQU 12
R13 EQU 13
R14 EQU 14
R15 EQU 15
END RBSRCH
Două mașini, aceeași idee
Pe PDP-11, recursivitatea curge natural: stiva hardware face totul transparent. Fiecare apel e doar un JSR, fiecare întoarcere e doar un RTS. Mașina a fost gândită pentru asta.
Pe /360, recursivitatea e ca un cort montat de mână în furtună: se poate, dar trebuie să știi unde bagi fiecare țăruș. Stiva simulată, cadrele pre-alocate, lanțul de Save Area-uri — toate sunt construcții pe care PDP-11 le avea gratuit în hardware.
Dar algoritmul? Algoritmul e același. Împarte, compară, cheamă-te pe tine însuți cu o problemă mai mică. Aceeași logică, indiferent dacă stiva e din siliciu sau din cod scris cu mâna.
Algoritmul etern nu ține cont de arhitectură. El doar funcționează.