Blog

Recursive Algorithm/ Recursion Algorithm Explained with Examples

In the world of computer science, algorithms are the backbone of any program. Among various types of algorithms, the recursive algorithm or the recursion algorithm stand out due to their elegant and efficient approach to solving problems. Recursive algorithm is used to solve problems by breaking them down into smaller instances of the same problem, making them useful for a wide range of applications.

In this detailed guide, we will explore what the recursive algorithm is, how they work, their advantages and disadvantages, and how you can implement them in Java. This guide is beginner-friendly but also offers deeper insights for those who want to understand recursion at a more advanced level.

What is a Recursive Algorithm?

A recursive algorithm is an algorithm that solves a problem by solving smaller instances of the same problem. It works by calling itself with a modified input, gradually reducing the problem’s size until it reaches a base case, which ends the recursion.

Key Components of the Recursive Algorithm:

  1. Base Case: This is the condition that stops the recursion. The recursion ends when the problem reduces to a form that can be directly solved (like a number equals 0 or 1).
  2. Recursive Case: This part involves solving a smaller version of the problem and making a recursive call. Consequently, the recursive call should always progress toward the base case.

How the Recursive Algorithm Works

Consider the process of looking for a book in a large stack. Instead of going through the entire stack at once, you pick up the first book, check if it’s the one you’re looking for, and if not, you continue with the remaining stack. This is similar to how the recursion algorithm or recursive algorithm works, where you repeatedly solve a smaller version of the problem until you reach the simplest version (the base case).

Also check: Sliding Window Algorithm – Fixed and Variable-Length Solutions

Examples of the Recursive Algorithm

Now that you know what is the recursive algorithm, let’s look at some examples to help you understand the concept a bit better.

Example 1: Factorial Calculation Using the Recursive Algorithm

Problem: Calculate the factorial of a number

The factorial of a number n (denoted as n!) is defined as the product of all positive integers from 1 to n. Mathematically:

  • n! = n × (n-1)! for n > 1
  • Base cases: 1! = 1 and 0! = 1

Step-by-Step Breakdown:

Let’s calculate the factorial of 5 using recursion. Here’s how the recursive function works:

Code:

public class Factorial {
    public static int factorial(int n) {
        // Base case: If n is 0 or 1, return 1
        if (n == 0 || n == 1) {
            return 1;
        } else {
            // Recursive case: n * factorial of (n-1)
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        int number = 5;
        int result = factorial(number);
        System.out.println("The factorial of " + number + " is: " + result);
    }
}

Execution Flow:

Recursive Algorithm
  1. First Call: factorial(5)
    • n is 5, so it doesn’t hit the base case.
    • The function proceeds to call factorial(4).
    • It returns 5 * factorial(4).
  2. Second Call: factorial(4)
    • n is 4, so it doesn’t hit the base case.
    • It calls factorial(3).
    • It returns 4 * factorial(3).
  3. Third Call: factorial(3)
    • n is 3, so it doesn’t hit the base case.
    • It calls factorial(2).
    • It returns 3 * factorial(2).
  4. Fourth Call: factorial(2)
    • n is 2, so it doesn’t hit the base case.
    • It calls factorial(1).
    • It returns 2 * factorial(1).
  5. Fifth Call: factorial(1)
    • n is 1, so it hits the base case.
    • The function returns 1.

Now, the recursion begins to unwind:

  • factorial(1) returns 1 = 1
  • factorial(2) returns 2 * 1 = 2
  • factorial(3) returns 3 * 2 = 6
  • factorial(4) returns 4 * 6 = 24
  • factorial(5) returns 5 * 24 = 120

Final Output:

The factorial of 5 is: 120.

Summary of Steps:

Base Case: If n == 0 or n == 1, return 1.

Recursive Case: Multiply n by the result of factorial (n – 1).

The recursion algorithm or recursive algorithm continues until it reaches the base case, and then it multiplies the results as the recursion ‘unwinds’ back through each level.

Also check: Greedy Algorithm: A Comprehensive Guide With Examples

Example 2: Fibonacci Sequence Using the Recursive Algorithm

Problem: Calculate the nth Fibonacci number.

The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones. Hence, the Fibonacci sequence is defined as:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) for n > 1

Step-by-Step Breakdown:

Let’s calculate the 6th Fibonacci number (F(6)) using recursion.

Code:

public class Fibonacci {
    public static int fibonacci(int n) {
        // Base cases
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            // Recursive case
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        int number = 6;
        int result = fibonacci(number);
        System.out.println("The Fibonacci number at position " + number + " is: " + result);
    }
}

Execution Flow:

  1. First Call: fibonacci(6)
    • n is 6, so it proceeds to the recursive case.
    • It calls fibonacci(5) and fibonacci(4).
    • The function returns fibonacci(5) + fibonacci(4).
  2. Second Call: fibonacci(5)
    • n is 5, so it proceeds to the recursive case.
    • It calls fibonacci(4) and fibonacci(3).
    • The function returns fibonacci(4) + fibonacci(3).
  3. Third Call: fibonacci(4)
    • n is 4, so it proceeds to the recursive case.
    • It calls fibonacci(3) and fibonacci(2).
    • The function returns fibonacci(3) + fibonacci(2).
  4. Fourth Call: fibonacci(3)
    • n is 3, so it proceeds to the recursive case.
    • It calls fibonacci(2) and fibonacci(1).
    • The function returns fibonacci(2) + fibonacci(1).
  5. Fifth Call: fibonacci(2)
    • n is 2, so it proceeds to the recursive case.
    • It calls fibonacci(1) and fibonacci(0).
    • The function returns fibonacci(1) + fibonacci(0).
  6. Sixth Call: fibonacci(1)
    • n is 1, so it returns 1 (base case).
  7. Seventh Call: fibonacci(0)
    • n is 0, so it returns 0 (base case).

Now the recursion starts unwinding and returning values:

  • fibonacci(0) returns 0 = 0
  • fibonacci(1) returns 1 = 1
  • fibonacci(2) returns 1 + 0 = 1
  • fibonacci(3) returns 1 + 1 = 2
  • fibonacci(4) returns 2 + 1 = 3
  • fibonacci(5) returns 3 + 2 = 5
  • fibonacci(6) returns 5 + 3 = 8

Final Output:

The Fibonacci number at position 6 is: 8

Summary of Steps:

Base Case: If n == 0, return 0; if n == 1, return 1.

Recursive Case: The Fibonacci number at position n is the sum of the Fibonacci numbers at positions n – 1 and n – 2.

The recursion continues until it reaches the base cases, and then it combines the results as the recursion unwinds.

Performance Considerations: Optimizing Recursive Algorithm

Problem with the Fibonacci Recursive Algorithm:

While the recursive Fibonacci algorithm works, it is inefficient for larger n values due to the recalculation of the same Fibonacci numbers multiple times. For example, fibonacci(2) is computed twice, fibonacci(3) is computed twice, and so on. Thus resulting in exponential time complexity.

Optimization of the Recursive Algorithm for Fibonacci with Memoization:

Memoization is a technique where we store the results of function calls, so we don’t have to recompute them. As a result, this improves performance by reducing redundant calculations.

Code with Memoization:

import java.util.HashMap;

public class FibonacciOptimized {
    private static HashMap<Integer, Integer> memo = new HashMap<>();

    public static int fibonacci(int n) {
        // Check if the result is already computed
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // Base cases
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }

        // Recursive case with memoization
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);  // Store the result in the map

        return result;
    }

    public static void main(String[] args) {
        int number = 6;
        int result = fibonacci(number);
        System.out.println("The Fibonacci number at position " + number + " is: " + result);
    }
}

How Memoization Optimizes the Process:

  • Memoization stores results in a HashMap (memo) as the recursion proceeds.
  • Before each recursive call, it checks if the result for fibonacci(n) is already stored. If it is, the result is returned directly without further recursion.
  • This reduces the time complexity to O(n), as each Fibonacci number is computed only once.

Final Output (with Memoization):

The Fibonacci number at position 6 is: 8

Advantages and Disadvantages of the Recursive Algorithm

Advantages of the Recursive Algorithm:

  1. Simplicity: Recursion simplifies the implementation of many problems, especially those involving hierarchical data (like trees or graphs) or problems that can be broken down into smaller subproblems.
  2. Elegance: Problems like tree traversal, graph search, and sorting often have a natural recursive structure. As a result, the code becomes more elegant and easier to read.
  3. Cleaner Code: Recursive solutions can often be shorter and more readable than their iterative counterparts, making them easier to understand and maintain.

Disadvantages of the Recursive Algorithm:

  1. Performance Issues: Recursive calls can cause performance problems due to the overhead of function calls, especially when dealing with large input sizes. Recursive functions use the call stack, which can lead to stack overflow errors if the recursion goes too deep.
  2. Memory Usage: Each recursive call requires memory on the call stack. If the recursion depth is too large, this can lead to memory inefficiency and crashes.
  3. Harder to Debug: Debugging recursive algorithms can be difficult because of the multiple function calls and the way the stack evolves during execution.

Practical Applications of the Recursion Algorithm

Recursion is a fundamental technique in computer science. Hence making it useful in many real-world applications. Here are a few areas where recursion is commonly used:

  1. Tree Traversal: Many data structures, like trees (e.g., binary trees), can be traversed effectively using recursion. In binary tree traversal, for example, you visit the left subtree, process the current node, and then visit the right subtree.
  2. Graph Traversal: Recursion is used in graph algorithms like depth-first search (DFS) and breadth-first search (BFS). DFS, for example, explores a graph by visiting a node and recursively visiting its neighbors.
  3. Divide and Conquer Algorithms: Algorithms such as quicksort and mergesort use recursion to break the problem into smaller subproblems, solve them, and combine the results.
  4. Backtracking: Recursion is frequently used in backtracking algorithms, such as solving N-Queens problems or solving Sudoku puzzles.

Performance Optimization: Memoization and Dynamic Programming

While recursion is elegant, it can be inefficient for certain problems. One way to optimize recursion is through memoization—a technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again.

For example, a recursive Fibonacci implementation can be optimized by storing previously computed Fibonacci numbers in an array or map, avoiding redundant calculations.

import java.util.HashMap;

public class FibonacciOptimized {
    private static HashMap<Integer, Integer> memo = new HashMap<>();

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }

        if (memo.containsKey(n)) {
            return memo.get(n); // Return cached result
        }

        // Recursive case with memoization
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result); // Store the result
        return result;
    }

    public static void main(String[] args) {
        int number = 6;
        int result = fibonacci(number);
        System.out.println("The Fibonacci number at position " + number + " is: " + result);
    }
}

By caching the results, we reduce redundant recursive calls, making the algorithm more efficient.

Important Problems Based on The Recursion Algorithm

The recursion algorithm can solve many problems. Here are some important ones, along with the companies that asked these questions (in brackets).

Conclusion

Recursive algorithms are a powerful and elegant way to solve problems, particularly when the problem can be broken down into smaller subproblems of the same type. For example, from calculating factorials and Fibonacci numbers to solving more complex problems like tree traversal, recursion provides both simplicity and elegance in coding.

However, it’s important to understand the trade-offs associated with recursion, such as performance and memory issues. Hence in practice, recursion is often paired with techniques like memoization and dynamic programming to optimize performance.

By following the examples and best practices shared in this guide, you can master recursive algorithms and use them effectively in your Java programming projects. Furthermore, keep practicing, and you’ll soon recognize the powerful ways recursion can simplify complex problems!

That’s all on the Recursion algorithm.

To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.

Please follow us on Medium.

Further Reading

This Post Has 2 Comments

Comments are closed.