Recursion in Java

Recursion is a programming technique where a method calls itself to solve smaller instances of a larger problem. It is widely used in computer science for tasks that can be broken down into smaller, similar subproblems. The recursive approach involves defining a base case to stop the recursion and a recursive step where the method calls itself.

How recursion works?

At its core, recursion works by dividing a problem into two parts:

1. Base Case: The condition that stops further recursion. This is the simplest instance of the problem, for which the answer is already known. Without a base case, recursion would continue indefinitely, leading to a stack overflow error.
2. Recursive Case: The part of the function which calls itself. The function will continue to call itself until the base case is reached.

What is the Call Stack?

The call stack is a data structure used by most programming languages to manage function calls and track their execution. It operates in a Last In, First Out (LIFO) manner, meaning the last function called is the first to be completed and removed from the stack.

When a function is called, the following happens:

1. The function's details, such as parameters, local variables, and the return address, are pushed onto the stack.
2. When the function finishes execution, the program returns to the calling function, and the function's information is removed(popped) from the stack.

In recursive functions, each recursive call is added to the stack until the base case is reached. Once the base case returns a result, the stack starts to unwind, resolving each recursive call in reverse order.

Example: Factorial Calculation in Java

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It is defined as:

• n! = n * (n-1) * ... * 2 * 1 (iteratively)
• n! = n * (n-1)! with base case 0!=1 (recursively)

Here is how we can use recursion to calculate the factorial of a number:

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

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

1. Base Case: When n == 0, the function returns 1 (since 0! = 1).
2. Recursive Case: When n > 0, the function calls itself with n - 1 and multiplies it by n.
3. Recursive Flow: For n = 5, the flow would be:
   • factorial(5) = 5 * factorial(4)
   • factorial(4) = 4 * factorial(3)
   • factorial(3) = 3 * factorial(2)
   • factorial(2) = 2 * factorial(1)
   • factorial(1) = 1 * factorial(0) (Base case reached, returns 1)

The recursive calls then resolve and the final result is computed as 5 * 4 * 3 * 2 * 1 = 120.