Concept of recursion

Recursion is a problem-solving technique where a function solves a problem by calling itself with a smaller instance of the same problem. Any algorithm that can be solved iteratively with a loop can also be solved recursively, and vice versa.

Every valid recursive function must have two distinct parts:

1. The Base Case: The trivial stopping condition where the answer is known directly without any further recursive calls. Without a base case, the function calls itself indefinitely until all call stack memory is exhausted.
2. The Recursive Step: The part of the function where it calls itself, passing a parameter that is closer to the base case (e.g. fact(n - 1)).

// Factorial: n! = n * (n - 1)!
public int factorial(int n) {
    // 1. Base case
    if (n <= 1) {
        return 1;
    }
    // 2. Recursive step
    return n * factorial(n - 1);
}

While recursion provides elegant solutions for nested trees and divide-and-conquer algorithms, it carries physical memory costs:

• Memory overhead: Each recursive invocation pushes a new stack frame onto the call stack. For deep recursion ($n = 10,000$), this triggers a StackOverflowError.
• Execution speed: Function call overhead (pushing/popping frames, setting up parameters) makes simple recursion slightly slower than a hardware-optimized iterative for loop.