Recursion

What is Recursion? #

Recursion can be defined as the process of defining something in terms of itself. A function that calls itself is called a recursive function.

A function that continues to call itself indefinately can end up consuming a lot of memory and the program can crash. Therefore, it is important to have a base case that stops the recursion. The base case is a condition that stops the recursion from continuing indefinitely.

myfunction(parameter) {
    if (base case) {
        return something;
    }
    return myfunction(parameter - 1);
}

What Problems can be solved using Recursion? #

While not always the go-to method, recursion excels in specific scenarios:

• Tree Traversals: Efficiently navigating through branching structures like trees, such as file systems or webpages.
• Divide-and-Conquer Algorithms: Splitting complex problems into smaller, independent subproblems, like quicksort for sorting data.
• Generating Recursive Structures: Creating data structures naturally defined recursively, like linked lists or binary search trees.
• Solving Algorithmic Puzzles: Offering elegant and concise solutions for problems like the Tower of Hanoi or Fibonacci sequence.

Factorial Example using Recursion #

A factorial of a number is the product of all the positive integers from 1 to that number. The factorial of a number n is denoted as n! and is calculated as:

n! = n * (n-1) * (n-2) * ... * 1

The factorial of 0 is 1.

In Java, a factiorial method could be implemented as follows:

public int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

The base case, or stopping condition, is when n is equal to 0. In this case, the method returns 1. Otherwise, the method calls itself with n - 1 as the argument.

Recursion is calculated in reverse #

When a recursive method is called, the method is pushed onto the call stack. When the base case is reached, the method is popped off the call stack and the result is calculated. The result is then passed back to the previous method on the call stack. This process continues until the original method is reached and the final result is returned.

In other words, the result of the method is calculated in reverse order.

If we to calculate the factorial of 5, we would probably perform the following steps:

result = 5 * 4
result = 20 * 3
result = 60 * 2
result = 120 * 1

In recursion, the calculations are performed in reverse order:

result = 1
result = 2 * 1
result = 3 * 2
result = 4 * 6
result = 5 * 24

Visualizing Recursion #

Here is a diagram that shows the call stack when the factorial method is called with the argument 5.

Production - Recursion vs Iteration #

Although recursion is sometimes more elegant and easier to understand, it is not always the best choice. Recursion can be less efficient than iteration because of the overhead of maintaining the call stack. In some cases, recursion can lead to a stack overflow error.

In production code, it is important to consider the trade-offs between recursion and iteration.

In production, care must be taken when choosing resursion over iteration. Diagnoising and debugging recursive code can be more difficult than iterative code. It is important that all edge cases are considered and tested.

Consider edge cases when testing recursive code.

In the factiorial example using recursion, if the input is a negative number, the method will continue to call itself indefinitely. Therefore, a check for input validation is important. For example, the factiorial method could be implemented as follows:

public int factorial(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Input must be a non-negative number");
    }
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

In contrast, the iterative version of the factiorial method does not have the same problem.

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

Summary #

Although recursion is a powerful concept that can be used to solve a variety of problems, it is not always the best choice. In production code, it is important to consider the trade-offs between recursion and iteration. Diagnoising and debugging recursive code can be more difficult than iterative code, and comprehehensive testing is important.