Java Recursion

Recursion in Java

Recursion is a programming technique where a method calls itself to solve a problem. Recursive solutions involve breaking a problem into smaller, similar subproblems, often with a base case to stop the recursion.

Recursive function examples:

• Calculating factorial.
• Traversing a tree data structure.

Recursion is a powerful programming technique in Java (and other programming languages) where a method calls itself to solve a problem. It is a fundamental concept in computer science and can be applied to various scenarios. Here's an explanation of recursion in Java with examples.

Key Concepts:

• Base Case: In a recursive function, there must be a base case, which is the termination condition. When the base case is met, the recursion stops, preventing infinite calls.
• Recursive Case: In the recursive function, there is a call to itself with a modified version of the problem. This is the step that breaks the problem into smaller, more manageable subproblems.

public class Factorial {
    public int factorial(int n) {
        // Base case: factorial of 0 or 1 is 1
        if (n == 0 || n == 1) {
            return 1;
        }
        // Recursive case: n! = n * (n-1)!
        else {
            return n * factorial(n - 1);
        }
    }

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

• In this example, we calculate the factorial of a number (n) recursively.
• The base case checks if n is 0 or 1, in which case the factorial is 1 (0! = 1 and 1! = 1).
• In the recursive case, we calculate n! as n multiplied by the factorial of n-1.
• The method calls itself with a smaller value (n-1) until it reaches the base case.

public class Fibonacci {
    public int fibonacci(int n) {
        // Base cases: Fibonacci of 0 and 1 is the number itself
        if (n <= 1) {
            return n;
        }
        // Recursive case: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
        else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        Fibonacci fib = new Fibonacci();
        int result = fib.fibonacci(7);
        System.out.println("Fibonacci number at position 7 is: " + result);
    }
}

• In this example, we calculate the Fibonacci sequence recursively.
• The base case is when n is 0 or 1, in which case the Fibonacci number is the same as n.
• In the recursive case, we calculate the Fibonacci number at position n as the sum of the Fibonacci numbers at positions n-1 and n-2.
• The method calls itself with smaller values (n-1 and n-2) until it reaches the base case.

Recursion is a powerful technique for solving problems that can be broken down into smaller, similar subproblems. It often leads to elegant and concise code but should be used with caution to avoid stack overflow errors when handling large inputs.