Chapter 10 - Recursion

Overview
Discussion
Factorial Example - Recursion using one parameter.
Power Example - Recursion using two parameters.
Fibonacci
Ackermann's Example - Multiple recursive calls.
Linked List Example

List Data Structure
Dynamic Memory Allocation
Recursive Tail Insertion
Recursive Printing of List
Main Procedure

Overview

In general, recursion requires that each activation of a function have its own data, usually consisting of the parameters to the function and any localized data such as local variables. This data is often termed the activation record of the function. A recursive function that had been called or activated five times would have five activation records, one for each activation. Activation records are allocated on entry to a function and deallocated on exit, most easily implemented by use of the stack, pushing parameters onto the stack prior to a function call and dynamically allocating and deallocating localized data on entry and exit to the function. This is consistent with the parameter passing methods of call-by-value and call-by-reference developed earlier (Homework 6) and followed by most recursive languages (e.g. Pascal, C++). The following examples are consistent with these methods.

Discussion

A series of examples below serve to illustrate the details of recursion and its common elements. The general assembly language elements of the calling a recursive function are the same as calling a non-recursive function as in the following:

**Calling procedure**
invoke Function, Parameters	Push Parameters Call Function Add eSp, <Number of Parameter bytes>

The recursive function differs from non-recursive functions only in that the recursive function contains a call to itself.

**Recursive function**
Function Proto Near C, Parameters if: Terminating Condition is true then: base case result else: recursive case result Push Parameters invoke Function, Parameters endif: Ret Function Endp	Function Proc Near Push eBp Mov eBp, eSp if: Terminating Condition is true then: base case result else: recursive case result Push Parameters Call Function Add eSp, <Number of Parameter bytes> endif: Pop eBp Ret Function Endp

Recursive function

Function  Proto     Near C, Parameters

  if:     Terminating Condition is true
   then:  base case result
   else:  recursive case result
          Push      Parameters
          invoke   Function, Parameters    
  endif:          
          Ret
Function Endp

Function Proc      Near
          Push      eBp
          Mov       eBp, eSp

  if:     Terminating Condition is true
   then:  base case result
   else:  recursive case result
          Push      Parameters
          Call     Function
          Add       eSp, <Number of Parameter bytes>
  endif:          
          Pop       eBp
          Ret
Function Endp

Exercise

Write a function in C++ using Recursion to print numbers from n to 0.
Write a function in Assembler using Recursion to print numbers from 0 to n.

Factorial Example

The recursive definition of the factorial function is:

0! = 1
n! = n * (n-1)!

Note that:

(n-1)! = (n-1) * (n-2)!

so for:

n = 3    3! = 3*2!
n = 2    2! = 2*1!
n = 1    1! = 1*0!
n = 0    0! = 1 by definition

**Factorial Example**
#include <iostream.h> int Fact(int N) { if( N <= 0) return 1; // base case result else return N*Fact(N-1); // recursive case result } void main(void) { cout << Fact(3); }
Title Fact - Recursive function with one parameter, n! .386 .model flat, stdcall PutDec proto .code Fact Proto Near C, N:dword ;; int Fact(int N) { @@if: Cmp N , 0 ;; If (N <= 0) Jle @@then ;; Fact = 1; Jmp @@else ;; Else Fact = N * Fact(N-1); @@then: Mov eAx, 1 Jmp @@endIf @@else: Mov eCx, N ;; Fact( N-1 ) * N Dec eCx invoke Fact, eCx Mul N ;; eAx = eAx * N @@endIf: Ret Fact Endp Main Proc near invoke Fact, 3 ;; eAx = Fact( 3 ); Call PutDec ;; cout << eAx; invoke ExitProcess, 0 Main Endp End Main	;; ___________ ;; \| 0003 \| <- eBp+8 ;; \|___________\| ;; 1st \|Return Addr\| <- eBp+4 ;; Call\|___________\| ;; \| eBp \| <- eBp ;; \|___________\|_________ N=3 ;; \| 0002 \| <- eBp+8 ;; \|___________\| ;; 2nd \|Return Addr\| <- eBp+4 ;; Call\|___________\| ;; \| eBp \| <- eBp ;; \|___________\|_________ N=2 ;; \| 0001 \| <- eBp+8 ;; 3rd \|___________\| ;; Call\|Return Addr\| <- eBp+4 ;; \|___________\| ;; \| eBp \| <- eBp ;; \|___________\|__________N=1 ;; \| 0000 \| <- eBp+8 ;; 4th \|___________\| ;; Call\|Return Addr\| <- eBp+4 ;; \|___________\| ;; \| eBp \| <- eBp ;; \|___________\|__________N=0

Factorial Example

#include <iostream.h>

int Fact(int N) {
        if( N <= 0) return 1;         // base case result
        else return N*Fact(N-1);     // recursive case result
}
                    
void main(void) {
        cout << Fact(3);
}

Title Fact - Recursive function with one parameter, n!
.386
.model flat, stdcall
       PutDec   proto
.code

Fact     Proto  Near C, N:dword  ;; int Fact(int N) {    
  
 @@if:   Cmp    N , 0           ;; If (N <= 0)
         Jle    @@then          ;;  Fact = 1;
         Jmp    @@else          ;; Else Fact = N *  Fact(N-1);
 @@then: Mov    eAx, 1
         Jmp    @@endIf
 @@else: Mov    eCx, N          ;; Fact( N-1 ) * N
         Dec    eCx                   

         invoke Fact, eCx            

         Mul  N                 ;; eAx = eAx * N
 @@endIf:
         Ret                        
Fact    Endp

Main  Proc     near

      invoke  Fact, 3         ;;  eAx = Fact( 3 );

      Call     PutDec           ;; cout << eAx;
      invoke   ExitProcess, 0
Main  Endp

      End      Main


;;      ___________             
;;     |   0003    | <- eBp+8    
;;     |___________|            
;; 1st |Return Addr| <- eBp+4   
;; Call|___________|            
;;     |  eBp      | <- eBp       
;;     |___________|_________ N=3
;;     |   0002    | <- eBp+8     
;;     |___________|
;; 2nd |Return Addr| <- eBp+4
;; Call|___________|
;;     |  eBp      | <- eBp
;;     |___________|_________ N=2
;;     |   0001    | <- eBp+8
;; 3rd |___________|
;; Call|Return Addr| <- eBp+4
;;     |___________|
;;     |  eBp      | <- eBp
;;     |___________|__________N=1
;;     |   0000    | <- eBp+8
;; 4th |___________|
;; Call|Return Addr| <- eBp+4
;;     |___________|
;;     |  eBp      | <- eBp
;;     |___________|__________N=0

Power Example

**Power Function**
#include <iostream.h> int Power(int X, int N) { if( N == 0 ) return 1; else return Power( X, N-1) * X; } void main(void) { cout << Power(5,2); }
Title Power - Recursive function with two parameters, x^n PutDec proto .code Power Proto Near C, X:dword, N:dword ;; int Power( int X, int N) { @@if: Cmp N , 0 ;; if (N == 0) Je @@then ;; return 1; Jmp @@else ;; else return Power(X,N-1) * X @@then: Mov eAx, 1 Jmp @@endIf @@else: Mov eCx, N ;; Power( X,N-1 ) * X Dec eCx invoke Power, X, eCx Mul X ;; eAx = eAx * X @@endIf: Ret Power Endp Main Proc near invoke Power, 5, 2 ;; eAx = Power( 5, 2 ); Call PutDec ;; cout << Ax invoke ExitProcess, 0 Main Endp End Main	;; _____________________ ;; N \| 2 \| <- eBp+12 ;; \|___________\| ;; X \| 5 \| <- eBp+8 ;; \|___________\| ;; \|Return Addr\| <- eBp+4 ;; 1st \|___________\| ;; Call\| eBp \| <- eBp+0 X=5 ;; ___\|___________\|___________N=2 ;; N \| 1 \| <- eBp+12 ;; \|___________\| ;; X \| 5 \| <- eBp+8 ;; \|___________\| ;; \|Return Addr\| <- eBp+4 ;; 2nd \|___________\| ;; Call\| eBp \| <- eBp+0 X=5 ;; ___\|___________\|___________N=1 ;; N \| 0 \| <- eBp+12 ;; \|___________\| ;; X \| 5 \| <- eBp+8 ;; \|___________\| ;; \|Return Addr\| <- eBp+4 ;; 3rd \|___________\| ;; Call\| eBp \| <- eBp+0 X=5 ;; ___\|___________\|___________N=0

Power Function

#include <iostream.h>

int Power(int X, int N) {
        if( N == 0 ) return 1;
        else return Power( X, N-1) * X;
}
                    
void main(void) {
        cout << Power(5,2);
}

Title    Power - Recursive function with two parameters, x^n
         PutDec   proto
.code

Power   Proto   Near C, X:dword, N:dword

                                ;; int Power( int X, int N) {  
 @@if:   Cmp    N , 0           ;; if (N == 0)
         Je     @@then          ;;  return 1;
         Jmp    @@else          ;; else return Power(X,N-1) * X
 @@then: Mov    eAx, 1
         Jmp    @@endIf
 @@else: Mov    eCx, N          ;; Power( X,N-1 ) * X       
         Dec    eCx                       

         invoke Power, X, eCx                    

         Mul    X               ;; eAx = eAx * X
 @@endIf:
         Ret                            
Power   Endp

Main  Proc     near

      invoke  Power, 5, 2     ;; eAx = Power( 5, 2 );

      Call     PutDec           ;; cout << Ax
      invoke   ExitProcess, 0
Main  Endp
      End      Main

;;      _____________________
;;  N  |     2     | <- eBp+12
;;     |___________|               
;;  X  |     5     | <- eBp+8       
;;     |___________|               
;;     |Return Addr| <- eBp+4       
;; 1st |___________|               
;; Call|   eBp     | <- eBp+0  X=5
;;  ___|___________|___________N=2
;;  N  |     1     | <- eBp+12
;;     |___________|
;;  X  |     5     | <- eBp+8  
;;     |___________|
;;     |Return Addr| <- eBp+4
;; 2nd |___________|
;; Call|   eBp     | <- eBp+0  X=5
;;  ___|___________|___________N=1
;;  N  |     0     | <- eBp+12
;;     |___________|
;;  X  |     5     | <- eBp+8      
;;     |___________|
;;     |Return Addr| <- eBp+4
;; 3rd |___________|
;; Call|   eBp     | <- eBp+0  X=5
;;  ___|___________|___________N=0

Exercise

Write a function in C++ using Recursion to check if a number n is prime. (You have to check whether n is divisible by any number below n)
Write the same function in Assembler.

Fibonacci

Recursive functions with more than one point of recursion may require that several function call results be combined. For example, Fibonacci's algorithm is discussed in the text and is defined as:

    Fibonacci(1) = 1
    Fibonacci(2) = 1
    Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

There are two recursive calls with each producing a result. The result of the first call must be combined with the result of the second call using addition. For n=3:

    Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = 1 + 1

The result of Fibonacci(2) must be temporarily saved, Fibonacci(1) computed, and the results of the two calls combined using addition. In Assembler:

invoke  Fibonacci, 2

Push   eAx           ; Save Fibonacci(2) result

invoke  Fibonacci, 1

Pop    eBx           ; Restore Fibonacci(2) result
Add     eAx, eBx      ; Combine Fibonacci(2) + Fibonacci(1)

The following figure gives the C++ algorithm and the results generated from each level of the recursive calls.

**Fibonacci in C++ and Recursive Call Tree and Assembler**
#include <iostream.h> int Fib(int n) { if (n == 1) return 1; if (n == 2) return 1; return Fib(n-1) + Fib(n-2); } void main(void) { cout << Fib(5); } Tree of recursive calls for Fib(5)	Title Recursive Fibonacci .386 .model flat, stdcall PutDec proto .code Fib Proto Near C, N:dword ;; int Fib(int N) @@if: Cmp N, 2 Jle @@then Jmp @@else @@then: Mov eAx, 1 ;; return 1 Jmp @@endif @@else: Mov eCx, n ;; return Fib(n-1)+Fib(n-2) Sub eCx,1 invoke Fib, eCx Push eAx ;; save Fib(n-1) Mov eCx, n Sub eCx, 2 invoke Fib, eCx ;; Fib(n-2) Pop eBx ;; recover Fib(n-1) Add eAx, eBx @@endif: Ret Fib Endp Main Proc near invoke Fib, 5 Call PutDec ;; cout << Fib ( 5 ); invoke ExitProcess, 0 Main Endp End Main

Fibonacci in C++ and Recursive Call Tree and Assembler

#include <iostream.h>

int Fib(int n) {
    if (n == 1) return 1;
    if (n == 2) return 1;
    return Fib(n-1) + Fib(n-2);
}

void main(void) {
    cout << Fib(5);
}

Tree of recursive calls for Fib(5)

Title     Recursive Fibonacci
.386
.model flat, stdcall
          PutDec    proto
.code

Fib       Proto      Near C, N:dword  ;; int Fib(int N) 
 @@if:    Cmp       N, 2 
          Jle       @@then 
          Jmp       @@else 
 @@then:  Mov       eAx, 1       ;; return 1 
          Jmp       @@endif 
 @@else:  Mov       eCx, n       ;; return Fib(n-1)+Fib(n-2) 
          Sub       eCx,1 

          invoke   Fib, eCx 
          Push     eAx         ;; save Fib(n-1) 

          Mov       eCx, n 
          Sub       eCx, 2

          invoke   Fib, eCx   ;; Fib(n-2) 

          Pop      eBx         ;; recover Fib(n-1) 
          Add       eAx, eBx  
 @@endif:  
          Ret  
Fib       Endp 

Main      Proc     near

          invoke   Fib, 5 

          Call     PutDec        ;; cout << Fib ( 5 ); 
          invoke   ExitProcess, 0  
Main      Endp

          End      Main

Exercise

Write a function in C++ using Recursion to compute binomial coefficients C(n, k) using the recursive definition:

C(n,n) = 1
C(n,0) = 1
C(n,k) = C(n-1, k-1) + C(n-1,k) for (0<k<n) and n>1
Write the same function in Assembler.

Ackermann's Example

Some algorithms require nested recursion where the result of one function call is a parameter to another function call. For example Ackermann's function is defined as:

A(m,n) = n + 1 if m == 0
A(m,n) = A(m-1, 1) if m > 0 && n == 0
A(m,n) = A(m-1, A(m, n-1)) if m > 0 && n > 0

Note functions return a result in the eAx register. The inner nested function result in eAx should be pushed onto the stack as a parameter to the outer nested function. For m=9 and n=7:

; A(9,7) = A(8,A(9,6))

  invoke  A, 9, 6     ;A(9,6)

  invoke  A, 8, eAx   ; A(8, A(9,6))

It is particularly interesting, for computational reasons, the depth of recursion due to the nested expression:

Ackermann( m-1, Ackermann(m, n-1))

For example, the execution of Ackermann(3,2) produces recursion of depth 30.

**Ackermann's Function**
#include <iostream.h> int Ackermann(int m, int n) { if(m==0) return n+1; else if (m>0 && n==0) return Ackermann(m-1,1); else if (m>0 && n>0) return Ackermann( m-1, Ackermann(m, n-1)); } void main(void) { cout << Ackermann(3,2); }
Title Ackermann's function - Recursive function with multipule recursions PutDec proto .code Ackermann Proto Near C, m:dword, n:dword ; int Ackermann(int m, int n) { @@if1: Cmp m , 0 ; if (m == 0) Je @@then1 Jmp @@else1 @@then1: Mov eAx, n ; Ackermann = n+1; Inc eAx Jmp @@endIf1 @@else1: ; else @@if2: Cmp m, 0 ; if (m > 0 && n == 0) Ja @@and2 Jmp @@else2 @@and2: Cmp n, 0 Je @@then2 Jmp @@else2 @@then2: Mov eCx, m Dec eCx ; Ackermann = Ackermann(m-1, 1); invoke Ackermann, eCx, 1 Jmp @@endif2 @@else2: ; else @@if3: Cmp m, 0 ; if (m > 0 && n > 0) Ja @@and3 ; Ackermann = Jmp @@endif3 ; Ackermann(m-1, Ackermann(m, n-1)) @@and3: Cmp n, 0 ; Endif Ja @@then3 ; Endif Jmp @@endif3 ; Endif @@then3: Mov eCx, n Dec Cx ; eAx = Ackermann(m, n-1) invoke Ackermann, m, eCx Mov eCx, m Dec eCx ; eAx = Ackermann(m-1, eAx) invoke Ackermann, eCx, eAx @@endif3: @@endif2: @@endif1: Ret ; Remove current m, n from stack Ackermann Endp Main Proc near invoke Ackermann, 3, 2 ; eAx := Ackermann( 3, 2 ); Call PutDec ; cout << eAx invoke ExitProcess, 0 Main Endp End Main

Ackermann's Function

#include <iostream.h>

int Ackermann(int m, int n) {
        if(m==0) return n+1;
        else if (m>0 && n==0) return Ackermann(m-1,1);
             else if (m>0 && n>0) return Ackermann( m-1, Ackermann(m, n-1));
}
                    
void main(void) {
        cout << Ackermann(3,2);
}

Title     Ackermann's function - Recursive function with multipule recursions
          PutDec   proto
.code
Ackermann Proto  Near C, m:dword, n:dword 
                                   ; int Ackermann(int m, int n) {
 @@if1:   Cmp  m , 0               ; if (m == 0)
          Je   @@then1               
          Jmp  @@else1                
 @@then1: Mov  eAx, n              ;   Ackermann = n+1;
          Inc  eAx                  
          Jmp  @@endIf1              
 @@else1:                          ;  else
  @@if2:       Cmp     m, 0        ;   if (m > 0 && n == 0)
               Ja      @@and2         
               Jmp     @@else2        
    @@and2:    Cmp     n, 0         
               Je      @@then2        
               Jmp     @@else2
    @@then2:                       
               Mov     eCx, m
               Dec     eCx
			           ;     Ackermann = Ackermann(m-1, 1);
               invoke  Ackermann, eCx, 1

               Jmp     @@endif2
   @@else2:                        ;   else   
     @@if3:    Cmp     m, 0        ;    if (m > 0 && n > 0)
               Ja      @@and3      ;         Ackermann = 
               Jmp     @@endif3    ;          Ackermann(m-1, Ackermann(m, n-1))
     @@and3:   Cmp     n, 0        ;     Endif
               Ja      @@then3     ;    Endif
               Jmp     @@endif3    ;  Endif
     @@then3:  Mov     eCx, n       
               Dec     Cx          ; eAx = Ackermann(m, n-1) 

               invoke  Ackermann, m, eCx
 
               Mov     eCx, m
               Dec     eCx         
				   ; eAx = Ackermann(m-1, eAx)
               invoke  Ackermann, eCx, eAx
     @@endif3:
  @@endif2:
@@endif1:
          Ret                      ; Remove current m, n from stack
Ackermann Endp

Main      Proc     near

          invoke  Ackermann, 3, 2 ;   eAx := Ackermann( 3, 2 );

          Call     PutDec          ;   cout << eAx
          invoke   ExitProcess, 0
Main      Endp

          End      Main

Exercise

Modify the C++ algorithm to determine the total number of calls.
Do the same for the Assembler algorithm.

**Linked List**
Title Linked list - Allocation, insertion and printing ;; Insert - Insert into a linked list ;; Print - Print a linked list ;; New - Allocate storage for dynamic data structure. Allocates ;; from static array of bytes (HEAP) by incrementing pointer ;; (Avail) by the number of bytes to allocate, always pointing ;; to the next available byte to allocate.
List Data Structure Example .386 .model flat, stdcall .xcref .nolist include c:\masm32\include\kernel32.inc include c:\masm32\include\masm32.inc includelib c:\masm32\lib\kernel32.lib includelib c:\masm32\lib\masm32.lib .list NULL Equ -1 HEAPSIZE Equ 200 ;; Allocateable memory size Link Struc ;; struct Link { Next dd NULL ;; Link Next; Value dd ? ;; word Value; Link Ends ;; }; .data ;; byte Heap[HEAPSIZE] Heap db HEAPSIZE dup (?) ;; Head dd ? ;; Link Head; Avail dd Heap ;; Avail points to Heap PutDec proto GetDec proto NewLine proto New proto near C, N:dword .code
Recursive Tail Insertion Example Insert Proto Near C, P:near ptr Link, Item:dword ; void Insert( Link P, int Item ) Mov eBx, P ;; if (p == NULL) @@if: Cmp dword ptr [eBx], NULL Je @@then Jmp @@else @@then: invoke New, Size Link Mov [eBx], eAx ;; { p = new Link(); Mov eBx, eAx Mov eAx, Item ;; p->Value = Item; Mov [eBx].Link.Value, eAx Mov [eBx].Link.Next, NULL Jmp @@endif ;; p->Next = NULL; @@else: ;; } Mov eBx, P ;; else Insert( p->Next, Item); invoke Insert, [eBx].Link.Next, Item @@endif: Ret Insert Endp
Recursive Printing of List Example Print Proto Near C, P:near ptr Link ;; void Print( Link P) @@if: Cmp P, NULL ;; If (p != NULL) Jne @@then Jmp @@endif @@then: Mov eBx, P Mov eAx, [eBx].Link.Value Call PutDec ;; { cout << p->Value); Call NewLine invoke Print, [eBx].Link.Next @@endif: ;; Print( p->Next ); Ret ;; } Print Endp
Dynamic Memory Allocation Example ; Link& New( int N ); ; N - Number of byte to allocate New Proto Near C, N:dword ;; Allocates N bytes from data area Mov eAx, N ;; Number of bytes to allocate Add eAx, Avail ;; Point to next available area @@if: Cmp eAx, offset Heap + HEAPSIZE Jae @@then ;; If Heap exhausted Jmp @@else ;; then New = 0 @@then: Mov eAx, 0 ;; else New = Avail Jmp @@endif ;; Avail = Avail + N @@else: Xchg eAx, Avail ;; Current available to Ax, next available @@endif: ;; to Avail Ret New Endp
Main Procedure Example Main Proc near Mov Head, NULL ;; Head = NULL Call GetDec ;; cin >> eAx ; @@while: Cmp eAx, 0 ;; while (eAx > -1) { Jg @@do ;; Insert( Head, eAx ); Jmp @@endwhile ;; cout << eAx; @@do: ;; } invoke Insert, addr Head, eAx ;; Print( Head ); Call GetDec Jmp @@while @@endwhile: invoke Print, Head invoke ExitProcess, 0 Main Endp End Main

Document last modified:

Chapter 10 - Recursion

Overview

Discussion

Exercise

Factorial Example

Power Example

Exercise

Fibonacci

Exercise

Ackermann's Example

Exercise

Linked List Example

List Data Structure Example

Recursive Tail Insertion Example

Recursive Printing of List Example

Dynamic Memory Allocation Example

Main Procedure Example