| Fibonacci(1) = 1 Fibonacci(2) = 1 Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) |
 |
Chapter 8Advanced Procedures
|
Modified: |
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 and followed by most recursive languages (e.g. Pascal, C++). The following examples are consistent with these methods.
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:
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.
Function Proc C, Parameters .IF Terminating Condition is true base case result .ELSE recursive case result invoke Function, Parameters .ENDIF Ret Function Endp |
Function Proc Push eBp Mov eBp, eSp .IF Terminating Condition is true base case result .ELSE recursive case result Push Parameters Call Function Add eSp, <Number of Parameter bytes> .ENDIF Pop eBp Ret Function Endp |
The recursive definition of the factorial function is:0! = 1Note that:
n! = n * (n-1)!(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
#include <iostream.h>
int Fact(int N) {
if( N <= 1) 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!
.code
Fact Proc Near C, N:dword ;; int Fact(int N) {
.IF N <= 1 ;; If (N <= 1)
Mov eAx, 1 ;; return 1
.ELSE ;; Else return N*Fact(N-1);
Mov eCx, N
Dec eCx
invoke Fact, eCx
Mul N
.ENDIF
Ret
Fact Endp
Main Proc near
invoke Fact, 3 ;; eAx = Fact( 3 );
Call WriteDec ;; 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 |
Example
#include <iostream.h>
int Sum(int N) {
if( N == 0) return 0; // base case result
else return N+Sum(N-1); // recursive case result
}
void main(void) {
cout << Sum(3);
}
|
.code
Sum Proc C, N:dword ;; int Sum(int N) {
.IF N == 0 ;; If (N == 0)
Mov eAx, 1 ;; return 0
.ELSE ;; Else return N+Sum(N-1);
Mov eCx, N
Dec eCx
invoke Sum, eCx
Add eAx, N
.ENDIF
Ret
Fact Endp
Main Proc near
invoke Sum , 3 ;; eAx = Sum( 3 );
Call WriteDec ;; cout << eAx;
invoke ExitProcess, 0
Main Endp
End Main
|
Question
Write a function in C++ (or method in Java) using
Recursion to print numbers from n to 0.
Write a function in C++ (or method in Java) using Recursion to print numbers
from 0 to n.
Write a function in Assembler using Recursion to print
numbers from n to 0.
#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
.code
Power Proc Near C, X:dword, N:dword
;; int Power( int X, int N) {
.IF N == 0 ;; if (N == 0)
Mov eAx, ;; return 1
.ELSE
Mov eCx, N ;; else
Dec eCx ;; return Power( X,N-1 ) * X
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 WriteDec ;; 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 |
Question
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 positive number less than n, other than 1).
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 defined as:
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(1) = 1
Fibonacci(2) = 1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = 1 + 1The 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) |
#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);
}
|
Title Recursive Fibonacci
.code
Fib Proc Near C, N:dword ;; int Fib(int N)
.IF N <= 2
Mov eAx, 1 ;; return 1
.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 WriteDec ;; cout << Fib ( 5 );
invoke ExitProcess, 0
Main Endp
End Main
|
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.
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 == 0Note 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(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
; 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.
#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
.code
Ackermann Proc Near C, m:dword, n:dword
; int Ackermann(int m, int n) {
.IF m == 0 ; if (m == 0)
Mov eAx, n ; return n+1;
Inc eAx
.ELSE ; else
.IF m > 0 && n == 0 ; if (m > 0 && n == 0)
Mov eCx, m
Dec eCx
; return Ackermann(m-1, 1);
invoke Ackermann, eCx, 1
.ELSE ; else
.IF m > 0 && n > 0 ; if (m > 0 && n > 0)
; return Ackermann(m-1, Ackermann(m, n-1))
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
.ENDIF
.ENDIF
.ENDIF
Ret
Ackermann Endp
Main Proc near
invoke Ackermann, 3, 2 ; eAx := Ackermann( 3, 2 );
Call WriteDec ; cout << eAx
invoke ExitProcess, 0
Main Endp
End Main
|
Exercise - http://en.wikipedia.org/wiki/McCarthy_91_function
McCarthy 91, defined by computer scientist John McCarthy as a test case for formal verification within computer science.
The results of evaluating the function are given by M(n) = 91 for all integer arguments n ≤ 101, and M(n) = n − 10 for n > 101.
Implement the following M function in Assembler.
McCarthy 91 Function #include <iostream.h> int M(int n) { if( n > 100) return n-10; else if (n <= 100) return M( M(n+11)); } void main(void) { cout << M(1000); }
Binary Search Exercise
Implement the following Binary Search function in Assembler.
Binary Search // pre: $key ^ $low ^ $high ^ $A0
// "j: 1 £ j £ n-1, Aj-1 £ Aj A[] sorted low to high// post: "j: 0 £ j £ n-1, Aj ¹ key ® result = -1 if key != A[j] then result = -1
// XORk: 0 £ k £ n-1, Ak = key ® result = k else key==A[k] then result = k
int BinarySearch (A, key, low, high) {
if (low > high) return -1;
int mid=(low+high)/2;
if (key == A[mid]) return mid;
if (key > A[mid])
return BinarySearch(A, key, mid+1, high);
else return BinarySearch(A, key, low, mid-1);
}
int X[] = {2, 4, 5, 7, 8, 9, 12, 14, 17, 19, 22, 25, 27, 28, 33};
void main () {
cout << BinarySearch(X, 18, 0, 14);
}
Linked List Example
