## 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.