Chapter 15 :Recursion(Part 1)

Welcome to Chapter 15 of our Data Structures and Algorithms (DSA) series, where we will dive into the concept of Recursion. In this chapter, we will explore how recursion works, its applications, and its implementation in Java. Recursion is a fundamental technique used in many problem-solving approaches in DSA, especially when breaking down complex problems into simpler, repeatable steps.

What is Recursion?

Recursion: A Detailed Theory Explanation

Before diving deep into recursion, it's essential to understand two foundational concepts:

Iteration (Loops): A process that repeats a block of code multiple times until a condition is met.
Functions: A block of code designed to perform a specific task, which can be called whenever needed in a program.

Recursion and iteration are two approaches to solve problems, but their application depends on the nature of the problem and the efficiency requirements. Both techniques have their strengths, and deciding between them often involves considering factors like time complexity and problem structure.

Recursion is particularly useful in advanced data structures like trees, graphs, and dynamic programming (DP). Problems involving these structures are often easier to solve with recursion because they naturally involve breaking down a complex problem into smaller sub-problems.

What is Recursion in Mathematics?

Let's first understand recursion with a mathematical example. Suppose we have the following function F(x):

If x = 2,
F(x) = x^2 = 2^2 = 4.
Now if we recursively call F(F(x)) (meaning we apply the function again on the result of F(x)):
F(F(x)) = (x^2)^2 = (2^2)^2 = 4^2 = 16.

This is the essence of recursion: a function calling itself repeatedly, like in this example, where the function F(x) calls itself.

Recursion with an Example: Factorial Function

Recursion can be better understood with a classic example: calculating the factorial of a number.

The factorial of a number n, denoted as n!, is defined as:

F(n) = n * F(n - 1)
F(0) = 1 (Base case)

So, for F(5), the recursion would proceed as follows:

F(5) = 5 * F(4)
F(4) = 4 * F(3)
F(3) = 3 * F(2)
F(2) = 2 * F(1)
F(1) = 1 * F(0)
F(0) = 1 (Base case reached)

At this point, the recursion starts returning values back up the chain:

F(1) = 1
F(2) = 2 * 1 = 2
F(3) = 3 * 2 = 6
F(4) = 4 * 6 = 24
F(5) = 5 * 24 = 120

Recursion Tree for Factorial (F(5))

The recursion process can be visualized using a recursion tree:

Apologies for missing the tree diagram earlier! Let’s create a recursion tree diagram for calculating the factorial of 5 (F(5)) to help visualize how recursion breaks down the problem and then combines solutions.

Factorial Recursion Tree for F(5)

Let's consider the recursive function for calculating the factorial:

F(n) = n * F(n - 1)
Base case: F(0) = 1

For F(5), the tree would look like this:

F(5)
├── F(4)
│   ├── F(3)
│   │   ├── F(2)
│   │   │   ├── F(1)
│   │   │   │   └── F(0)

This is how the recursion tree will expand:

At the top level, we start with F(5). To calculate F(5), we need to calculate F(4).
Next level, we need F(4) to calculate F(5). So, F(4) calls F(3) to get its result.
At each level, the function keeps calling itself with a smaller value, breaking down the problem into smaller and smaller sub-problems, until the base case is reached.
Once we hit the base case (F(0) = 1), the recursion stops, and the answers start returning back up the tree:
- F(1) = 1 * F(0) = 1
- F(2) = 2 * F(1) = 2
- F(3) = 3 * F(2) = 6
- F(4) = 4 * F(3) = 24
- F(5) = 5 * F(4) = 120

Visual Representation (Recursion Tree)

                            F(5)
                           /    \
                      5 * F(4)   (Waiting for result of F(4))
                           |
                      4 * F(3)   (Waiting for result of F(3))
                           |
                      3 * F(2)   (Waiting for result of F(2))
                           |
                      2 * F(1)   (Waiting for result of F(1))
                           |
                      1 * F(0)   (Base case: F(0) = 1)
                           |
                      Return 1    (Start returning results)
                      -----
                           |
                      F(1) = 1   (Result of F(1) = 1 * 1 = 1)
                           |
                      F(2) = 2   (Result of F(2) = 2 * 1 = 2)
                           |
                      F(3) = 6   (Result of F(3) = 3 * 2 = 6)
                           |
                      F(4) = 24  (Result of F(4) = 4 * 6 = 24)
                           |
                      F(5) = 120 (Result of F(5) = 5 * 24 = 120)

Explanation of the Tree:

Top to Bottom: The function keeps calling itself until it hits the base case F(0) = 1.
Bottom to Top: Once the base case is reached, the recursion starts returning results and combining them to get the final answer (F(5) = 120).

Definition of Recursion

Recursion is a method of solving a problem where the solution depends on the solution to smaller instances of the same problem. A recursive function typically has:

Base Case: The condition that terminates the recursion.
Recursive Case: The part where the function calls itself with a reduced problem size.

Base Case: The Key to Ending Recursion

The base case is the most crucial part of recursion. Without it, the function would continue to call itself infinitely, resulting in a stack overflow error. The base case ensures that the recursion eventually stops.

In the factorial example, the base case is when n = 0, where F(0) = 1. This condition halts further recursive calls, allowing the recursion to start returning results back up the call stack.

The Flow of Recursion

In recursion, there are two main phases:

Top to Bottom (Towards Base Case):
This is the phase where we make recursive calls to break down the problem. For example, to calculate F(5), we need to calculate F(4), and to calculate F(4), we need F(3), and so on, until we reach the base case.
Bottom to Top (Returning Values):
After reaching the base case, we start combining solutions. In the factorial example, once F(0) returns 1, we calculate F(1), then F(2), and so on, eventually calculating F(5).

How Recursion Works in a Program

To understand recursion from a programmatic perspective, let's visualize it with a main function and a recursive function:

The main function calls the recursive function for the first time.
The recursive function performs its task and makes another call to itself.
This process continues until the base case is hit, at which point the recursion starts returning results back up the call stack.

Summary of Recursive Structure

Recursion can be summarized in three essential steps:

Base Case: This is the stopping condition for the recursion.
Work to be Done: The task the function performs, such as calculating factorial.
Recursive Call: The function calls itself with a reduced problem size.

For example, in the factorial problem:

Base Case: When n = 0, return 1.
Work to be Done: Multiply n by the result of the recursive call.
Recursive Call: Call the function with n-1 until the base case is reached.

Recursion vs Iteration

Recursion and iteration (loops) can both be used to solve problems. However, certain problems, like tree traversal, graph exploration, and dynamic programming, are often easier to solve using recursion due to their divide-and-conquer nature. Choosing between recursion and iteration depends on the problem type and efficiency considerations:

Recursion can be more intuitive for problems involving hierarchical structures.
Iteration is generally more efficient for simpler, linear problems as it avoids the overhead of multiple function calls.

1. Print Numbers in Decreasing Order

To print numbers from n to 1 using recursion, we can follow these steps:

Base Case: If n becomes less than 1, stop the recursion.
Recursive Case: Print n, then call the function with n-1.

public static void printDecreasing(int n) {
    if (n < 1) {
        return;  // Base case
    }
    System.out.println(n);  // Print the current number
    printDecreasing(n - 1);  // Recursive call
}

For example, calling printDecreasing(5) will output:

2. Stack Overflow in Recursion

A stack overflow occurs when the recursive function doesn't reach the base case, or the problem is too large for the memory. Recursion relies on the system's call stack, and if the recursive calls are too deep, the program runs out of stack space, resulting in a stack overflow.

For instance, missing the base case in a recursive function will lead to infinite recursion:

public static void faultyFunction(int n) {
    System.out.println(n);
    faultyFunction(n - 1);  // No base case!
}

3. Print Numbers in Increasing Order

To print numbers from 1 to n using recursion:

Base Case: When n is less than 1, stop.
Recursive Case: First print the smaller numbers, then print n.

public static void printIncreasing(int n) {
    if (n < 1) {
        return;
    }
    printIncreasing(n - 1);  // Recursive call
    System.out.println(n);  // Print after recursion to get increasing order
}

Calling printIncreasing(5) will output:

4. Find Factorial of n

The factorial of a number n is the product of all integers from 1 to n. It can be computed recursively:

Base Case: If n is 0 or 1, return 1.
Recursive Case: Return n * factorial(n-1).

public static int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;  // Base case
    }
    return n * factorial(n - 1);  // Recursive call
}

5. Print Sum of First n Natural Numbers

To compute the sum of the first n natural numbers, you can use recursion:

Base Case: If n is 0, return 0.
Recursive Case: Return n + sum(n-1).

public static int sumOfNaturalNumbers(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sumOfNaturalNumbers(n - 1);
}

6. Print nth Fibonacci Number

The Fibonacci sequence is defined as:

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

The recursive function for finding the nth Fibonacci number is:

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

7. Check if Array is Sorted

To check if an array is sorted:

Base Case: If the array has only one element, it is sorted.
Recursive Case: Check if the first element is smaller than the next and recursively check the rest of the array.

public static boolean isSorted(int[] arr, int index) {
    if (index == arr.length - 1) {
        return true;
    }
    if (arr[index] > arr[index + 1]) {
        return false;
    }
    return isSorted(arr, index + 1);
}

8. Find First Occurrence of an Element

To find the first occurrence of a number in an array:

Base Case: If the index reaches the end, return -1.
Recursive Case: If the current element matches, return the index. Otherwise, continue to the next index.

public static int firstOccurrence(int[] arr, int index, int target) {
    if (index == arr.length) {
        return -1;  // Target not found
    }
    if (arr[index] == target) {
        return index;
    }
    return firstOccurrence(arr, index + 1, target);
}

9. Find Last Occurrence of an Element

To find the last occurrence of a number in an array:

Base Case: If the index reaches the end, return -1.
Recursive Case: First recursively check the rest of the array. If the element is found after, return that index. If not, check the current index.

public static int lastOccurrence(int[] arr, int index, int target) {
    if (index == arr.length) {
        return -1;
    }
    int restIndex = lastOccurrence(arr, index + 1, target);
    if (restIndex != -1) {
        return restIndex;
    }
    if (arr[index] == target) {
        return index;
    }
    return -1;
}

10. Print `x` to the Power of `n`

To calculate x^n using recursion:

Base Case: If n is 0, return 1.
Recursive Case: Return x * power(x, n-1).

public static int power(int x, int n) {
    if (n == 0) {
        return 1;
    }
    return x * power(x, n - 1);
}

11. Optimized Power Calculation (x^n)

An optimized way to calculate x^n is using divide and conquer:

Base Case: If n is 0, return 1.
Recursive Case: If n is even, return power(x, n/2) * power(x, n/2). If n is odd, return x * power(x, n/2) * power(x, n/2).

public static int optimizedPower(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int halfPower = optimizedPower(x, n / 2);
    if (n % 2 == 0) {
        return halfPower * halfPower;
    } else {
        return x * halfPower * halfPower;
    }
}

In the next part of this chapter, we'll continue our exploration of recursion with more complex problems and techniques. Stay tuned!

Related Posts in My Series:

DSA in Java Series:

Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.
Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.
Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

LinkedIn: Connect with me for professional updates and insights.
GitHub: Explore my repositories and contributions to various projects.
LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast