Java Tutorial

Operators

Flow Control

String

Number and Date

Built-in Classes

Array

Class and Object

Inheritance and Polymorphism

Exception Handling

Collections, Generics and Enumerations

Reflection

Input/Output Stream

Annotation

Java Recursive Algorithm

Recursion is a programming technique where a function calls itself to solve a problem. It can be an elegant and powerful approach when solving certain types of problems, such as divide-and-conquer algorithms, tree traversal, and combinatorial search. In this tutorial, we will cover the basics of recursion in Java and provide examples of recursive algorithms.

Anatomy of a recursive function:

A recursive function typically consists of two parts:

A base case: This is a condition that stops the recursion, usually by returning a simple result that does not require further recursion.
A recursive case: This is the part of the function that calls itself with a smaller or simpler problem.

Example: Computing the factorial of a number using recursion:

public static int factorial(int n) {
    if (n == 0) { // Base case: 0! = 1
        return 1;
    } else { // Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1);
    }
}

In this example, the base case is when n is equal to 0, and the function returns 1. The recursive case calls the factorial() function with the argument n - 1.

Example: Fibonacci sequence using recursion:

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The recursive function for the Fibonacci sequence can be defined as follows:

Base case: fib(0) = 0 and fib(1) = 1
Recursive case: fib(n) = fib(n-1) + fib(n-2) for n > 1

Here is an example implementation of the Fibonacci sequence using recursion in Java:

public static int fibonacci(int n) {
    if (n == 0) { // Base case 1: fib(0) = 0
        return 0;
    } else if (n == 1) { // Base case 2: fib(1) = 1
        return 1;
    } else { // Recursive case: fib(n) = fib(n-1) + fib(n-2)
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Limitations of recursion:

While recursion can provide elegant solutions to certain problems, it also has some limitations:

Stack overflow: Since each recursive call adds a new frame to the call stack, deep recursion can lead to a stack overflow error, causing the program to crash.
Performance: Recursive algorithms can be inefficient, especially when they involve a large number of redundant calculations, as in the naive implementation of the Fibonacci sequence.

To address these limitations, you can use techniques such as memoization (caching results of previous calls) or switch to an iterative approach.

In this tutorial, we covered the basics of recursion in Java and provided examples of recursive algorithms, including the factorial function and the Fibonacci sequence. Recursion is a powerful programming technique that can be used to solve a wide range of problems, but it also has some limitations, such as the risk of stack overflow and potential performance issues.

Java Recursive Method Call:

A recursive method calls itself, either directly or indirectly.

void recursiveMethod() {
    // Some base case to stop recursion
    recursiveMethod(); // Recursive call
}

Recursion in Java with Factorial Example:

Calculating factorial using recursion.

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

Binary Search using Recursion in Java:

Binary search algorithm implemented using recursion.

int binarySearch(int[] arr, int target, int low, int high) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, high);
        } else {
            return binarySearch(arr, target, low, mid - 1);
        }
    }
    return -1; // Element not found
}

Java Recursive Tree Traversal:

Tree traversal using recursion (in-order, pre-order, post-order).

class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int data) {
        this.data = data;
        left = right = null;
    }
}

void inOrderTraversal(TreeNode root) {
    if (root != null) {
        inOrderTraversal(root.left);
        System.out.print(root.data + " ");
        inOrderTraversal(root.right);
    }
}

Fibonacci Series with Recursion in Java:

Generating Fibonacci series using recursion.

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

Java Recursive File and Directory Traversal:

Traversing files and directories using recursion.

void listFiles(File directory) {
    File[] files = directory.listFiles();
    for (File file : files) {
        if (file.isDirectory()) {
            listFiles(file); // Recursive call
        } else {
            System.out.println(file.getName());
        }
    }
}

Java Recursive Data Structures:

Recursive data structures, such as linked lists and trees, involve self-referencing structures.

class ListNode {
    int data;
    ListNode next;

    ListNode(int data) {
        this.data = data;
        next = null;
    }
}

Maze-Solving Algorithm in Java using Recursion:

Solving a maze using recursion.

boolean solveMaze(int[][] maze, int x, int y, int[][] solution) {
    // Base cases and recursive calls
}

Merge Sort Algorithm in Java using Recursion:
- Sorting an array using the merge sort algorithm.
```
void mergeSort(int[] arr, int low, int high) {
    // Base case and recursive calls
}
```
Quicksort Implementation with Recursion in Java:
- Sorting an array using the quicksort algorithm.
```
void quickSort(int[] arr, int low, int high) {
    // Base case and recursive calls
}
```

Tower of Hanoi in Java with Recursion:

Solving the Tower of Hanoi problem using recursion.

void towerOfHanoi(int n, char source, char auxiliary, char target) {
    // Base case and recursive calls
}

Backtracking Algorithm with Recursion in Java:
- Solving problems with backtracking, such as the N-Queens problem.
```
boolean solveNQueens(int[][] board, int col) {
    // Base case and recursive calls
}
```