Q) Compute nCr using recursive procedure. Assume that ‘n’ and ‘r’ are non-negative integers.
This program will compute the ‘nCr’ value of a given input ‘n’ and ‘r’. The result is stored in AX register. View the output of the program in the debug screen.
Algorithm 1:
Step 1: if r=0 or n=r then nCr=1
Step 2: if r=1 or r=n-1 then nCr=n
Step 3: Recursive definition of nCr is “nCr= (n-1)Cr + (n-1)C(r-1)”
Algorithm 2:
nCr(r,n)
{
If(r==0 || n==r)
Return(1);
Else
If(r==1 || r==n-1)
Return(n);
Return(nCr (r,n-1)+ (n-1)Cr(r-1,n-1));
}
Same algorithm is given in two different ways. Whichever you like, go with it.
CODE:
Explanation:
- .MODEL SMALL
- .DATA
- N DW 5H
- R DW 3H
- NCR DW 0
Data segment with locations storing ‘n’ and ‘r’ values. Initially stored with two immediate values n=5 and r=3. (since we are gonna find 5C3 in this program).
NCR is a location holding the result and is of word length(2 bytes). Initially stored with the value 0.
- .CODE
- MOV AX,@DATA
- MOV DS,AX
- MOV AX,N
- MOV BX,R
‘N’ value is copied to AX register.
‘R’ copied to BX.
- CALL ENCR
- MOV AX,NCR
- MOV AH,4CH
- INT 21H
What is a procedure?
Its similar to the C routines/function. A small piece of assembly language code written in it and you can access it from the actual main code to perform some tasks.
So ENCR computed nCr and stores the result in NCR location. We move the result to AH register in order to view it from the debugging screen.
Then the program is terminated using 4CH into AH and on INT 21H.
Now, This is the actual code which performs the nCr operation. Be careful here.
This is the recursive procedure. BE CAREFUL.
As per the algorithm, we know some direct nCr values, (as if r=0 and r=n, then nCr=1).
So check for such conditions existence,
- ENCR PROC
- PARA1:
- CMP AL,BL
- JE PARA8
PARA1 is the label.
AL (which is ‘n’) is compared with BL (which is ‘r’) if they are equal. If they are, then we have the ready-made formula nCr=1. (according to the algorithm) this is done in PARA8. So jump to PARA8 if AL and BL are equal.
- PARA2:
- CMP BL,0
- JE PARA8
- PARA3:
- CMP BL,1
- JE PARA10
- PARA4:
- DEC AL
- CMP BL,AL
- JE PARA9
if( r==n-1)
nCr=n;
Check it here.
DEC AL decreases AL (which is ‘n’) by 1. In order to compare BL(which is ‘r’) with AL-1.
If equal, jump to PARA9 (JE PARA9) and set the result to n(by adding 1 and N-1, since N is decreased by 1 already, just now).
If none of the above ready-made formulas match, then compute the nCr using the recursive call according to the algorithm.
“(n-1)Cr + (n-1)Cr(r-1)”
We will split this into finding of “(n-1)Cr” first and then “(n-1)Cr(r-1)”- PARA5:
- PUSH AX
- PUSH BX
- CALL ENCR
AX and DX values are pushed in to the stack in order to take back up of them since they are gonna change during recursive calls and we want the original values back after recursion completes.
As we know, ‘R’ is in BX and ‘N-1’ is present in ‘AX’ (remember we decreased ‘n’ by 1 in the above step while checking for ready-made formula existence. So no need to change it again).
With the new values of ‘n’ and ‘r’, call ENCR again.
- PARA6:
- POP BX
- POP AX
- DEC BL
- PUSH AX
- PUSH BX
- CALL ENCR
Pop back AX and BX values from the stack to get the original values which were pushed during the previous computation(we had took back up of them in the stack).
Formula says, (n-1)C(r-1).
We had already decreased ‘n’ by 1. So this time only decrease ‘r’ by 1 using DEC BL instruction. (BL contains ‘r’).
Push back AX and DX to stack again to take a back up.
- PARA7:
- POP BX
- POP AX
- RET
Now only thing left out is what happens if ready-made formulas occur, Those were said to be defined in PARA8, PARA9 and PARA10 labels. But we never defined them. Go further and find them below.
PARA8 in the condition: If(r==0 || n==r)
PARA9 in the condition: If(r==n-1)
PARA10 in the condition: If(r==1)
- PARA8:
- INC NCR
- RET
The nCr in this case is 1. So increase NCR location by ‘1’.(add 1 to NCR) and return the control to the previous call.
- PARA9:
- INC NCR
The nCr in this case is ‘N’ itself. So increase NCR location by ‘1’ and add ‘N-1’ (value stored in AX) to it which is done in the next step.
Adding AX is because we had decreased n to n-1 during the process.
- PARA10:
- ADD NCR,AX
- RET
[but N is not decreased by 1, because it is done only in the condition of (r==n-1).. Check out]
The nCr in this case is ‘N’ itself. So NCR is added with N, which is stored in AX register.
[Important: If you are coming from PARA9 label, AX will be having N-1 remember. Thats why 1 is added in label PARA9 and here AX which contains ‘N-1’ is added]
However, finally NCR is added with ‘N’ and return the control to the previous call in both cases if(r==n-1) and if(r==1). We will return control to next recursion if any. Or else control will be passed to main code and value of NCR is copied to AH register which we can view in the debugging register.
- ENCR ENDP
- END
END is the end of the program.
Output:
Output is seen in Debugging screen using afdebug program.asm command in the prompt after compiling and linking the program’s object file.
Share your views about this article!