1. What is recursion
Recursion is when a function refers to itself within it own definition.
We can distinguish between two types of recursion:
Tail Recursion – the function first performs some processing and only then calls itself. Tail recursion is similar to a loop in that it performs all its computation before performing the next recursive call;
Head Recursion – any recursive function which is not Tail Recursive.
2. Recursion in Java
Recursion in Java is when a method calls itself within it own definition.
2.1 Head Recusrion Example
public int head(int n) {
// compute from n
int result1 = ...
// compute from n and result1
boolean condition = ...
if(condition) {
return head(result1);
}
// compute from n and result1
int result2 = ...
return result2;
}
2.2 Tail Recursion Example
public int tail(int n) {
// compute from n
int result1= ...
// compute from n and result1
boolean precondition = ...
if(precondition) {
return result1;
}
// compute from n and result1
int result2 = ...
return tail(result2);
}
3. Advantages of using Recursion in Java
Recursive methods are generally simpler to code and maintain than iterative methods.
4. Disadvantages of using Recursion in Java
Recursion requires that the method repeatedly pushes itself onto the Java stack. Recursion generally takes more memory than iterative methods. Also, if the recursion is too deep it will exhaust the capacity of the stack and result in a StackOverflowError.
5. Recursion vs Iteration vs Dynamic Programming
Simplicity
- Recursion: Often easier to implement and maintain.
- Iteration: Often difficult to implement and maintain.
- Dynamic Programming: Often easier to implement and maintain.
Performance
- Recursion: Often has poorer performance.
- Iteration: Iteration involves loops which the compiler can optimize. So iteration often has better performance.
- Dynamic Programming: Depends on the problem.
Memory
- Recursion: Generally takes more memory.
- Iteration: Often takes less memory.
- Dynamic Programming: Often takes less memory since one only stores the minimal amount of data required.
6. Examples
6.1 Fibonacci Sequence
The n-th term, f(n), of the Fibonacci sequence is defined as follows:
n = 0 : f(0) = 0
n = 1 : f(1) = 1
n > 1 : f(n) = f(n-2) + f(n-1)
It is easy to see that the first few terms of the Fibonacci sequence are
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Recursion version
public static int fibonacci(int n) {
switch(n) {
case 0: return 0;
case 1: return 1;
default: return fibonacci(n-2) + fibonacci(n-1);
}
}
Iteration version
public static int fibonacciIterationVersion(int n) {
switch(n) {
case 0: return 0;
case 1: return 1;
default:
int[] f = new int[n + 1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n + 1; i++) {
f[i] = f[i - 2] + f[i - 1];
}
return f[n];
}
}
Dynamic version
public static int fibonacciDynamicVersion(int n) {
switch(n) {
case 0: return 0;
case 1: return 1;
default:
int[] f = new int[3];
f[0] = 0;
f[1] = 1;
for (int i = 0; i < n; i++) {
f[2] = f[0] + f[1];
f[1] = f[0];
f[0] = f[2];
}
return f[2];
}
}
6.2 Factorials
The factorial of a non-negative integer n is written as n!. It is defined as fallows:
0! = 1
1! = 1
n! = n * (n-1)!
The first few factorials are
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
Recursion version
public static int factorialRecursionVersion(int n) {
switch(n) {
case 0: return 1;
case 1: return 1;
default: return n * factorialRecursionVersion(n-1);
}
}
Iteration version
public static int factorialIterationVersion(int n) {
switch(n) {
case 0: return 1;
case 1: return 1;
default:
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i < n + 1; i++) {
f[i] = i * f[i - 1];
}
return f[n];
}
}
Dynamic version
public static int factorialDynamicVersion(int n) {
switch(n) {
case 0: return 1;
default:
int result = 1;
for (int i = 1; i < n + 1; i++) {
result *= i;
}
return result;
}
}
7. Conclusion
In this article, we learned about recursive programming and compared it to iterative and dynamic programming.