Recursion
A recursive subroutine is one that may call itself to perform some subsidiary task.
If a subroutine is calling itself then it makes a new stack frame for each recursion.
Recursion may also appear in the form of mutual recursion.
Factorial Example
factorial(1) = 1
factorial(n) = n * factorial(n - 1)
In order to make a recursive function, you need a base case(to terminate execution) and some method to progress to the base case.
Implementation in Java
...
static int f(int n) {
if (n < 2) return 1;
return n * f(n - 1);
}
...
As an alternate to pattern matching we are using a if statement to make the decision.
Implementation in Assembly
This will multiply the top 2 items on the stack and leave the result in EAX:
multiply PROC
pop ebx
pop eax
mov tmp, eax
pop eax
mul eax, tmp
push ebx
ret
multiply ENDP
factorial PROC ; parameter n is passed via eax
cmp eax, 2 ; check if n < 2
jl rtn1
push eax ; push current value of n
dex eax ; decrease the value of n
call factorial ; recursively call factorial
push eax ; push the result
call multiply ; n * fac(n - 1)
ret ; return with result in eax
rtn1:
mov eax, 1 ; zero or one factorial is 1
ret ; return with result in eax
factorial ENDP
Consider computing the factorial of 3. Calling the sequence might be:
mov eax, 3
call factorial
// now eax contains result
This shows the parameters that are on the stack at each call:
