Unrolling the Recursion

Unrolling recursion involves expanding out the recursive calls into an iterative implementation. This eliminates function call overhead.

For example, recursive factorial:

factorial(n) 
  if n == 0:
    return 1
  else 
    return n * factorial(n-1)

Can be unrolled into iteration:

factorial(n):
  result = 1
  for i = 1 to n:
    result *= i
  return result

Java example unrolling Fibonacci recursion:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int fib(int n) {
  if (n <= 1) return n;

  int prev = 0;
  int curr = 1;

  for (int i = 2; i <= n; i++) {
    int temp = curr;
    curr += prev; 
    prev = temp;
  }

  return curr;
}

C++ example unrolling binary search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int binarySearch(vector<int> arr, int key) {
  
  int low = 0;
  int high = arr.size() - 1; 

  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (key < arr[mid]) {
      high = mid - 1;
    } else if (key > arr[mid]) {
      low = mid + 1; 
    } else {
      return mid; 
    }
  }

  return -1;
}

Python example unrolling power function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def power(a, b):
  
  result = 1
  while b > 0:
    if b % 2 == 1:
      result *= a
    a *= a
    b //= 2

  return result

Unrolling recursion removes function call overhead for improved performance.

Unrolling the recursion is an optimization technique used to make a recursive function more efficient by replacing it with an iterative version. This eliminates the overhead associated with recursive function calls, such as stack maintenance and function call overheads. This is particularly useful when the recursive calls are trivial or the recursive tree is shallow.

Java Code

Let’s consider calculating the factorial of a number using recursion and then unroll it.

Recursive Version

1
2
3
4

public static int factorialRecursive(int n) {
    if (n <= 1) return 1;
    return n * factorialRecursive(n - 1);
}

Unrolled Version

1
2
3
4
5
6
7

public static int factorialUnrolled(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

In the unrolled version, we use a for loop to eliminate the recursive calls, thereby reducing the overhead.

C++ Code

Recursive Version

1
2
3
4

int factorialRecursive(int n) {
    if (n <= 1) return 1;
    return n * factorialRecursive(n - 1);
}

Unrolled Version

1
2
3
4
5
6
7

int factorialUnrolled(int n) {
    int result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

Here too, we replace the recursive function with a simple loop to calculate the factorial.

Python Code

Recursive Version

1
2
3
4

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

Unrolled Version

1
2
3
4
5

def factorial_unrolled(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

In Python, the concept remains the same. The recursive function is replaced by an iterative one to remove the overhead of recursive calls.

By unrolling the recursion, we not only make the code more efficient but also easier to understand and debug, without affecting the functionality.