Recursion in Java (Complete Detailed Guide)

Introduction

Recursion DSA ka ek powerful concept hai jo beginners ko thoda confusing lag sakta hai, lekin agar ek baar samajh aa gaya to Tree, Graph, Backtracking, Dynamic Programming sab easy ho jate hain.

Recursion is a programming technique in which a function solves a problem by calling itself with a smaller or simpler input until a stopping condition is reached. Instead of using loops, recursion repeatedly breaks the problem into smaller subproblems of the same type. Each recursive call waits for the next call to finish before returning its result. Every recursive solution must contain a base case to stop execution and a recursive case to reduce the problem size. Recursion is widely used in tree traversal, divide-and-conquer algorithms, backtracking, and dynamic programming.

Aaj hum recursion ko bilkul simple language me samjhenge — real-life example ke saath.

What is Recursion?

Recursion is a programming technique in which a function calls itself to solve smaller instances of the same problem until a stopping condition is reached. Instead of solving the entire problem at once, recursion breaks it into smaller subproblems of the same type. Every recursive solution must have two main components: a base case (which stops the recursion) and a recursive case (which reduces the problem size). Recursion is widely used in algorithms like Merge Sort, Quick Sort, Tree Traversal, and Backtracking.

Two Important Parts of Recursion

Base Case
Ye wo condition hoti hai jahan recursion stop ho jata hai.
Agar base case nahi hoga, to program infinite loop me chala jayega (Stack Overflow error).
Recursive Case
Ye wo part hai jahan function khud ko call karta hai, lekin chhoti problem ke saath.

What is a Base Case?

A base case is the stopping condition in a recursive function that prevents infinite execution. It defines the simplest version of the problem where no further recursive calls are required. When the base case condition becomes true, the function stops calling itself and begins returning results back through the call stack. Without a base case, recursion will continue indefinitely, eventually causing a Stack Overflow error due to excessive memory usage in the call stack.

What is a Recursive Case?

A recursive case is the part of a recursive function where the function calls itself with a reduced input size. This step ensures that the problem gradually moves toward the base case. The recursive case must always modify the input in such a way that it eventually satisfies the base case condition. If the input does not reduce properly, recursion may never terminate. The recursive case is responsible for breaking down a large problem into smaller manageable subproblems of the same type.

What is Call Stack?

The call stack is a memory structure used by the system to keep track of active function calls during program execution. In recursion, each function call is pushed onto the stack, and when the function completes, it is removed (popped) from the stack. If too many recursive calls are made without reaching the base case, the stack memory gets full, resulting in a Stack Overflow error. Understanding the call stack is crucial for tracing recursive function execution.

Real Life Example (Student Friendly)

Socho tum mirror ke saamne khade ho aur mirror ke andar mirror hai.

Image repeatedly reflect hoti rehti hai.

Ye recursion jaisa hi hai — function khud ko repeat karta hai jab tak condition stop na kare.

Socho tum 5th floor par ho aur neeche ground floor tak jaana hai.

Tum har step par ek floor neeche jaate ho.

5 → 4 → 3 → 2 → 1 → 0

Ground floor base case hai.

Wapas aate waqt tum 0 → 1 → 2 → 3 → 4 → 5

Ye recursion ka flow hai.

Example 1: Factorial Using Recursion

Factorial formula:

n! = n × (n-1)!

Java Implementation


public class RecursionExample {

    static int factorial(int n) {
        if (n == 0 || n == 1)   // Base Case
            return 1;

        return n * factorial(n - 1);  // Recursive Case
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
}
Dry Run (factorial(3))
factorial(3)

= 3 × factorial(2)

= 3 × (2 × factorial(1))

= 3 × (2 × 1)

= 6

Example 2: Print Numbers from 1 to n


public class RecursionExample {

    static void printNumbers(int n) {
        if (n == 0)   // Base Case
            return;

        printNumbers(n - 1);  // Recursive Call
        System.out.println(n);
    }

    public static void main(String[] args) {
        printNumbers(5);
    }
}

Dry Run (n = 3)

Call Stack Flow:

print(3)
→ print(2)
→ print(1)
→ print(0) (base case hit)

Ab reverse order me print hoga:

1
2
3

How Recursion Works Internally?

Har recursive call stack memory me store hoti hai
Jab base case milta hai, stack unwind hota hai
Isi ko call stack kehte hain

Time Complexity

Recursion ka time complexity depend karta hai kitni baar function call ho raha hai.

Example above:
O(n)

Space Complexity

O(n)
Kyuki har function call stack me store hota hai.

Advantages of Recursion

Complex problems ko simple banata hai
Code simple aur readable hota hai
Complex logic short form me likh sakte hain.
Divide and Conquer algorithms me useful
Merge Sort, Quick Sort recursion use karte hain.

Tree and Graph problems ke liye powerful

Disadvantages

Stack overflow risk
Kabhi-kabhi iterative solution se slow
Stack Overflow risk
Agar base case galat ho.
Extra memory use karta hai
Har call stack me store hoti hai.

Kabhi iterative approach faster hoti hai

Recursion (Youtube)

Quick Check (Basic Interaction)

👉 Agar recursion me base case nahi diya jaye to kya hoga?

A) Program fast chalega
B) Infinite loop
C) Stack Overflow Error
D) Compilation Error

Comment me answer likho 👇

Search This Blog

CodeWithDeepak

Recursion in Java Explained with Examples (Base Case, Recursive Case & Dry Run Guide)