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 >