6.4 Recursion

 < Day Day Up > 



6.4 Recursion

A recursive procedure or function is one that calls itself, either directly or indirectly. The best algorithms for manipulating many data structures are recursive. It is frequently very difficult to code certain algorithms in a programming language that does not support recursion.

It is almost as easy to code a recursive procedure in 80x86 assembly language as it is to code a nonrecursive procedure. If parameters are passed on the stack and local variables are stored on the stack, then each call of the procedure gets new storage allocated for its parameters and local variables. There is no danger of the arguments passed to one call of a procedure being confused with those for another call since each call has its own stack frame. If registers are properly saved and restored, then the same registers can be used by each call of the procedure.

This section gives one example of a recursive procedure in 80x86 assembly language. It solves the Towers of Hanoi puzzle, pictured in Fig. 6.18 with four disks. The object of the puzzle is to move all disks from source spindle A to destination spindle B, one at a time, never placing a larger disk on top of a smaller disk. Disks can be moved to spindle C, a spare spindle. For instance, if there are only two disks, the small disk can be moved from spindle A to C, the large one can be moved from A to B, and finally the small one can be moved from C to B.

click to expand
Figure 6.18: Towers of Hanoi puzzle

In general, the Towers of Hanoi puzzle is solved by looking at two cases. If there is only one disk, then the single disk is simply moved from the source spindle to the destination. If the number of disks NbrDisks is greater than one, then the top (NbrDisks-1) disks are moved to the spare spindle, the largest one is moved to the destination, and finally the (NbrDisks-1) smaller disks are moved from the spare spindle to the destination. Each time (NbrDisks-1) disks are moved, exactly the same procedure is followed, except that different spindles have the roles of source, destination, and spare. Figure 6.19 expresses the algorithm in pseudocode.

start figure
   procedure Move(NbrDisks, Source, Destination, Spare);
   begin
          if NbrDisks = 1
          then
               display "Move disk from ", Source, " to ", Destination
          else
               Move(NbrDisks -- 1, Source, Spare, Destination);
               Move(1, Source, Destination, Spare);
               Move(NbrDisks -- 1, Spare, Destination, Source);
          end if;
   end procedure Move;
   begin {main program}
          prompt for and input Number;
          Move(Number, 'A', 'B', 'C');
   end;
end figure

Figure 6.19: Pseudocode for Towers of Hanoi Solution

Figure 6.20 shows 80x86 code that implements the design. The stack is used to pass parameters to procedure Move, which is a NEAR32 procedure referencing the data segment for output only. A standard stack frame is established, and registers used by the procedure are saved and restored. The code is a fairly straightforward translation of the pseudocode design. The operator DWORD PTR is required in the statement

start figure

; program to print instructions for "Towers of Hanoi" puzzle
; author: R. Detmer revised: 10/97

.386
.MODEL FLAT

ExitProcess PROTO NEAR32 stdcall, dwExitCode:DWORD

include io.h                 ; header file for input/output

cr      equ      0dh         ; carriage return character
Lf      equ      0ah         ; line feed

.STACK  4096                 ; reserve 4096-byte stack

.DATA                        ; reserve storage for data
prompt      BYTE   cr,Lf,'How many disks? ',0
number      BYTE   16 DUP (?)
message     BYTE   cr,Lf,'Move disk from spindle '
source      BYTE   ?
            BYTE   ' to spindle '
dest        BYTE   ?
            BYTE    '.',0
.CODE
Move        PROC   NEAR32
; procedure Move(NbrDisks : integer; { number of disks to move }
;           Source, Dest, Spare : character { spindles to use } )
; parameters are passed in words on the stack

            push   ebp           ; save base pointer
            mov    ebp,esp       ; copy stack pointer
            push   eax           ; save registers
            push   ebx

            cmp    WORD PTR [ebp+14],1 ; NbrDisks = 1?
            jne    elseMore      ; skip if more than 1
            mov    bx,[ebp+12]   ; Source
            mov    source,bl     ; copy character to output
            mov    bx,[ebp+10]   ; destination
            mov    dest,bl       ; copy character to output
            output message       ; print line
            jmp    endIfOne      ; return
elseMore:   mov    ax,[ebp+14]   ; get NbrDisks
            dec    ax            ; NbrDisks - 1
            push   ax            ; parameter 1: NbrDisks-1
            pushw  [ebp+12]      ; parameter 2: source does not change
            pushw  [ebp+8]       ; parameter 3: old spare is new destination
            pushw  [ebp+10]      ; parameter 4: old destination is new spare
            call   Move          ; Move(NbrDisks-1,Source,Spare,Destination)
            add    esp,8         ; remove parameters from stack

            pushw  1             ; parameter 1: 1
            pushw  [ebp+12]      ; parameter 2: source does not change
            pushw  [ebp+10]      ; parameter 3: destination unchanged
            pushw  [ebp+8]       ; parameter 4: spare unchanged
            call   Move          ; Move(1,Source,Destination,Spare)
            add    esp,8         ; remove parameters from stack


            push   ax            ; parameter 1: NbrDisks-1
            pushw  [ebp+8]       ; parameter 2: source is original spare
            pushw  [ebp+10]      ; parameter 3: original destination
            pushw  [ebp+12]      ; parameter 4: original source is spare
            call   Move          ; Move(NbrDisks-1,Spare,Destination,Source)
            add    esp,8         ; remove parameters from stack
endIfOne:
            pop    ebx           ; restore registers
            pop    eax
            pop    ebp           ; restore base pointer
            ret                  ; return
Move        ENDP

_start:     output prompt        ; ask for number of disks
            input  number,16     ; read ASCII characters
            atoi   number        ; convert to integer
            push   ax            ; argument 1: Number
            mov    al,'A'        ; argument 2: ' A'
            push   ax
            mov    al,'B'        ; argument 3: ' B'
            push   ax
            mov    al,'C'        ; argument 4: ' C'
            push   ax
            call   Move          ; Move(Number,Source,Dest,Spare)
            add    esp,8         ; remove parameters from stack

            INVOKE   ExitProcess, 0 ; exit with return code 0

PUBLIC _start                    ; make entry point public
END                              ; end of source code
 

end figure

Figure 6.20: Towers of Hanoi solution

     cmp   DWORD PTR [bp+14],1
 

so that the assembler knows whether to compare words or byte size operands. Similarly, the pushw mnemonic is used several places so that the assembler knows to push wordsize parameters. Notice that the recursive calls are implemented exactly the same way as the main program call, by pushing four parameters on the stack, calling procedure Move, then removing the parameters from the stack. However, in the main program the spindle parameters are constants, stored as the low order part of a word since single bytes cannot be pushed on the 80x86 stack.

Exercises 6.4

start example
  1. What will go wrong in the Towers of Hanoi program if EAX is not saved at the beginning of procedure Move and restored at the end?

  2. Suppose that the Towers of Hanoi program is executed and 2 is entered for the number of disks. Trace the stack contents from the first push in the main program through the instruction add esp,8 in the main program.

end example

Programming Exercises 6.4

start example
  1. The factorial function is defined for a non-negative integer argument n by

    Write a recursive assembly language procedure named Factorial that implements this recursive definition. Use the stack to pass the single doubleword integer argument; return the value of the function in the EAX register. The calling program should remove the parameter from the stack. Test your function by calling it from a main program that inputs an integer, calls the Factorial function, and displays the value returned by the function. Why is it better to use doubleword-size than word-size integers for this function?

  2. The greatest common divisor (GCD) of two positive integers m and n can be calculated recursively by the function described below in pseudocode. function GCD(m, n : integer) : integer;

    if n = 0
    then
       return m;
    else
       Remainder := m mod n;
       return GCD(n, Remainder);
    end if;
     

    Implement this recursive definition in assembly language. Use the stack to pass the two doubleword-size argument values. Return the value of the function in the EAX register. The procedure should remove the parameters from the stack. Test your function with a main program that inputs two integers, calls the greatest common divisor function GCD, and displays the value returned.

end example



 < Day Day Up >