• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Java Recursion

← Previous Next →

Recursion is a powerful programming concept in Java where a method calls itself to solve a problem. It is often used to break down complex problems into smaller, simpler ones. In many cases, recursive solutions are easier to write and understand than iterative ones, especially for problems involving repetitive patterns such as factorials, Fibonacci numbers, and tree traversals.

In simple terms, recursion means a method keeps calling itself until it reaches a certain condition that stops the calls. This condition is known as the base case.

What is Recursion in Java?

In Java, recursion happens when a method calls itself either directly or indirectly. It’s a way to perform repetitive tasks without using loops. A recursive method must always have a base case to prevent infinite recursion, which can lead to a stack overflow error.

Each time a method calls itself, a new stack frame is created in memory to store its variables and state. Once the base case is reached, the method starts returning results back through the stack, eventually reaching the original call.

Syntax of a Recursive Method

Here’s the basic syntax of recursion in Java:

void recursiveMethod() {
    // base case
    if (condition) {
        return;
    } else {
        // recursive call
        recursiveMethod();
    }
}

The base case stops further recursive calls, and the recursive call moves the process one step closer to that base case.

Example: Factorial Using Recursion

One of the most common examples to understand recursion is the factorial of a number. The factorial of n (written as n!) is the product of all positive integers less than or equal to n.

For example,
5! = 5 × 4 × 3 × 2 × 1 = 120

Here’s how you can calculate it using recursion:

class FactorialExample {
    static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1; // base case
        } else {
            return n * factorial(n - 1); // recursive call
        }
    }

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

In this example, each call to factorial() reduces the value of n until it reaches 1. Then, the function returns values back up the call stack, completing the multiplication.

How Recursion Works (Step-by-Step)

Let’s trace the above example for factorial(3):

  1. factorial(3) calls factorial(2)

  2. factorial(2) calls factorial(1)

  3. factorial(1) hits the base case and returns 1

  4. The result bubbles back: factorial(2) = 2 × 1 = 2

  5. Then, factorial(3) = 3 × 2 = 6

This step-by-step breakdown shows how recursive calls stack up and then unwind once the base case is reached.

Direct and Indirect Recursion

Recursion can be of two types:

1. Direct Recursion

When a method directly calls itself, it is known as direct recursion.
Example:

void display(int n) {
    if (n > 0) {
        System.out.println(n);
        display(n - 1); // direct recursion
    }
}

2. Indirect Recursion

When a method calls another method, and that second method again calls the first one, it’s called indirect recursion.
Example:

class IndirectExample {
    void methodA(int n) {
        if (n > 0) {
            System.out.println("A: " + n);
            methodB(n - 1);
        }
    }

    void methodB(int n) {
        if (n > 0) {
            System.out.println("B: " + n);
            methodA(n - 1);
        }
    }

    public static void main(String[] args) {
        IndirectExample obj = new IndirectExample();
        obj.methodA(3);
    }
}

Here, methodA() and methodB() keep calling each other until the base case is reached.

Common Use Cases of Recursion

Recursion is widely used in many areas of programming, such as:

  • Mathematical problems like factorial, Fibonacci, and power functions

  • Data structures such as trees and linked lists

  • Searching and sorting algorithms like quicksort and mergesort

  • Backtracking problems like solving mazes or generating permutations

Example: Fibonacci Series Using Recursion

The Fibonacci sequence is another classic recursion problem.
Fibonacci numbers are defined as:
F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)

class FibonacciExample {
    static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        int count = 7;
        for (int i = 0; i < count; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

This program prints the first seven Fibonacci numbers using recursion.

Advantages of Recursion

  • Reduces code length and improves readability for problems that have a repetitive structure.

  • Works naturally with problems that can be divided into smaller subproblems.

  • Eliminates the need for complex loop structures.

Disadvantages of Recursion

  • Each recursive call consumes memory in the call stack, which may lead to StackOverflowError if recursion is too deep.

  • It is often less efficient than iterative solutions due to repeated method calls.

  • Harder to debug when recursion depth is high.

Tail Recursion in Java

Tail recursion is a special form of recursion where the recursive call is the last statement in the method. This type of recursion can be optimized by some compilers to reuse stack frames, improving efficiency. However, Java doesn’t optimize tail recursion automatically.

Example:

class TailRecursionExample {
    static void printNumbers(int n) {
        if (n == 0) return;
        System.out.println(n);
        printNumbers(n - 1); // recursive call at the end
    }

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

Summary of the Tutorial

Recursion in Java is a concept where a method calls itself to solve a problem step by step. Each recursive call should have a base case to stop further calls. It helps simplify problems like factorial, Fibonacci, and searching algorithms but should be used carefully to avoid memory issues. Understanding recursion builds a strong foundation for advanced topics like algorithms and data structures.

Practice Questions

  1. Write a Java program to find the factorial of a number using recursion.

  2. Create a Java program that prints numbers from 1 to 10 using a recursive method.

  3. Write a recursive Java program that calculates the sum of all natural numbers up to a given number.

  4. Develop a Java program to find the nth Fibonacci number using recursion.

  5. Write a Java program that uses recursion to reverse a given string.

  6. Create a Java program to calculate the power of a number (x^y) using a recursive method.

  7. Write a recursive method in Java to count the number of digits in a given integer.

  8. Develop a Java program that uses recursion to find the greatest common divisor (GCD) of two numbers.

  9. Write a recursive Java program that checks whether a string is a palindrome or not.

  10. Create a recursive Java program that calculates the sum of elements in an integer array.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Java

online coding class codepractice

Java Basics

Java Variables & Data Types

Java Control Flow

Java Arrays

Java Methods

Java Classes & Objects

OOP Principles

Java Utilities

Error Handling

Collections Framework

Java File Handling

Advanced Java

codepractice logo
Login
Go Back Top