Introduction to Recursion

Recursion is a powerful technique in programming that involves a function calling itself. It is based on the principle of 'divide and conquer,' where a problem is broken down into smaller, more manageable subproblems.

In recursive algorithms, a problem is solved by solving smaller instances of the same problem, until a base case is reached where the problem can be directly solved without further recursion.

By using recursion, we can express complex problems in an elegant and concise manner by leveraging the repetitive nature of the problem.

Recursion is especially useful for problems that can be naturally defined in terms of smaller instances of the same problem. It allows us to tackle problems that may be difficult or cumbersome to solve using iterative approaches.

To illustrate the concept of recursion, let's consider the classic example of the Fibonacci sequence. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

Here's a Java code snippet that calculates the Fibonacci sequence using recursion:

1public class Fibonacci {
2  public int calculateFibonacci(int n) {
3    if (n <= 1) {
4      return n;
5    }
6
7    return calculateFibonacci(n - 1) + calculateFibonacci(n - 2);
8  }
9
10  public static void main(String[] args) {
11    Fibonacci fibonacci = new Fibonacci();
12    int n = 10;
13    for (int i = 0; i <= n; i++) {
14      System.out.println(fibonacci.calculateFibonacci(i));
15    }
16  }
17}

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    for(int i = 1; i <= 100; i++) {

      if(i % 3 == 0 && i % 5 == 0) {

          System.out.println("FizzBuzz");

      } else if(i % 3 == 0) {

          System.out.println("Fizz");

      } else if(i % 5 == 0) {

          System.out.println("Buzz");

      } else {

          System.out.println(i);

      }

    }

  }

}

Recursive Functions

Recursive functions are functions that call themselves. They are an important concept in programming, especially in the context of recursion. By calling themselves, recursive functions create recursive algorithms, which are algorithms that solve a problem by breaking it down into smaller instances of the same problem.

Recursive functions have two main components:

1. Base Case: This is the condition that determines when the recursion should stop. It is the simplest form of the problem that can be solved directly without further recursion.

2. Recursive Case: This is the condition where the function calls itself with a modified input. It represents the step towards the base case, taking the problem closer to its simplest form.

Let's take a look at an example to better understand recursive functions. Consider a function countDown that prints the numbers from a given number down to 1:

1public class Main {
2  public static void countDown(int n) {
3    // Base case: If n is less than or equal to 1, print n and return
4    if (n <= 1) {
5      System.out.println(n);
6      return;
7    }
8
9    // Recursive case: Print n and call the function with n - 1
10    System.out.println(n);
11    countDown(n - 1);
12  }
13
14  public static void main(String[] args) {
15    // Example call to countDown starting from 5
16    countDown(5);
17  }
18}

When we call countDown(5), it will print the numbers 5, 4, 3, 2, and 1 in that order.

Recursive functions can be a powerful tool for solving problems, as they allow us to express complex problems in a more manageable and elegant way. It's important to ensure that recursive functions have a base case that will eventually be reached, to avoid infinite recursion.

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

  // replace with your Java logic here

  for(int i = 1; i <= 5; i++) {

    System.out.println(i);

  }

}

}

Base Case and Recursive Case

In recursive functions, it is important to understand the difference between the base case and the recursive case. These two components play a crucial role in the functioning of recursive algorithms.

The base case is the condition that determines when the recursion should stop. It is the simplest form of the problem that can be solved directly without further recursion. It is like the exit condition for the recursive algorithm.

On the other hand, the recursive case is the condition where the function calls itself with a modified input. It represents the step towards the base case, taking the problem closer to its simplest form.

Let's take a look at the earlier example of the countDown function:

1public class Main {
2  public static void countDown(int n) {
3    // Base case: If n is less than or equal to 1, print n and return
4    if (n <= 1) {
5      System.out.println(n);
6      return;
7    }
8
9    // Recursive case: Print n and call the function with n - 1
10    System.out.println(n);
11    countDown(n - 1);
12  }
13
14  public static void main(String[] args) {
15    // Example call to countDown starting from 5
16    countDown(5);
17  }
18}

In this example, the base case is when n is less than or equal to 1. When this condition is met, the function simply prints n and returns, ending the recursion. This ensures that the recursion stops and the algorithm doesn't continue indefinitely.

On the other hand, the recursive case is when n is greater than 1. In this case, the function prints n and then calls itself with n - 1. This recursive call takes the problem closer to the base case by reducing n with each recursion.

By understanding the base case and recursive case, you can ensure that your recursive functions are well-defined and terminate properly.

xxxxxxxxxx

public class Main {

  public static void countDown(int n) {

    // Base case: If n is less than or equal to 1, print n and return

    if (n <= 1) {

      System.out.println(n);

      return;

    }

​

    // Recursive case: Print n and call the function with n - 1

    System.out.println(n);

    countDown(n - 1);

  }

​

  public static void main(String[] args) {

    // Example call to countDown starting from 5

    countDown(5);

  }

}

Factorial

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It is denoted by n!.

For example, the factorial of 5 (5!) is calculated as:

15! = 5 * 4 * 3 * 2 * 1 = 120

The factorial function is commonly implemented using recursion. The recursive definition of the factorial function is as follows:

• Base case: If n is 0 or 1, the factorial is 1.
• Recursive case: If n is greater than 1, the factorial is calculated as n multiplied by the factorial of n - 1.

Let's take a look at an example implementation of the factorial function in Java:

1public class Main {
2  public static int factorial(int n) {
3    // Base case: If n is 0 or 1, return 1
4    if (n == 0 || n == 1) {
5      return 1;
6    }
7
8    // Recursive case: Return n * factorial(n - 1)
9    return n * factorial(n - 1);
10  }
11
12  public static void main(String[] args) {
13    // Example call to factorial for n = 5
14    int result = factorial(5);
15    System.out.println(result);
16  }
17}

In this example, the factorial function takes an integer n as input and returns the factorial of n. The function uses recursion to calculate the factorial. The base case is when n is 0 or 1, in which case the function returns 1. The recursive case is when n is greater than 1. In this case, the function calculates the factorial of n by multiplying n with the factorial of n - 1. This recursive call continues until the base case is reached, resulting in the factorial of the original n.

Try running the example code to see the factorial of 5 being calculated and printed to the console.

xxxxxxxxxx

public class Main {

  public static int factorial(int n) {

    // Base case: If n is 0 or 1, return 1

    if (n == 0 || n == 1) {

      return 1;

    }

​

    // Recursive case: Return n * factorial(n - 1)

    return n * factorial(n - 1);

  }

​

  public static void main(String[] args) {

    // Example call to factorial for n = 5

    int result = factorial(5);

    System.out.println(result);

  }

}

xxxxxxxxxx

Output:

120

Fibonacci Series

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones. It starts with 0 and 1, and each subsequent number is the sum of the two previous numbers.

Here's an example of the Fibonacci series:

10, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The Fibonacci series can be implemented using recursion. The recursive definition of the Fibonacci series is as follows:

• Base case: If n is 0 or 1, return n.
• Recursive case: Return the sum of the two previous Fibonacci numbers.

Let's take a look at an example implementation of the Fibonacci series in Java:

{{code}}

In this example, the fibonacci function takes an integer n as input and returns the n-th Fibonacci number. The function uses recursion to calculate the Fibonacci number. The base case is when n is 0 or 1, in which case the function returns n. The recursive case is when n is greater than 1. In this case, the function calculates the Fibonacci number by summing the two previous Fibonacci numbers (fibonacci(n - 1) and fibonacci(n - 2)). This recursive call continues until the base case is reached, resulting in the desired Fibonacci number.

Try running the example code to see the 6th Fibonacci number being calculated and printed to the console.

xxxxxxxxxx

public class Main {

  public static int fibonacci(int n) {

    // Base case: If n is 0 or 1, return n

    if (n == 0 || n == 1) {

      return n;

    }

​

    // Recursive case: Return the sum of the two previous Fibonacci numbers

    return fibonacci(n - 1) + fibonacci(n - 2);

  }

​

  public static void main(String[] args) {

    // Example call to fibonacci for n = 6

    int result = fibonacci(6);

    System.out.println(result);

  }

}

Binary Search

Binary search is a widely used search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array and repeatedly divides the search interval in half to narrow down the search range.

The binary search algorithm can be implemented using recursion. Here's an example implementation in Java:

{{code}}

In this example, the binarySearch function takes an integer array arr and a target value target as input. It calls the recursive helper function binarySearch with additional parameters start and end, initially set to the first and last indices of the array.

The base case of the recursion is when start becomes greater than end, indicating that the target value is not found in the current search range. In this case, the function returns -1.

In the recursive case, the function calculates the middle index (mid) of the current search range and compares the value at arr[mid] with the target value. If they are equal, the function returns the index mid. If the target value is less than arr[mid], the function makes a recursive call to search the left half of the array (start remains the same, end becomes mid - 1). If the target value is greater than arr[mid], the function makes a recursive call to search the right half of the array (start becomes mid + 1, end remains the same).

Try running the example code to see binary search in action. It searches for the value 5 in the sorted array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and prints the index at which it is found.

xxxxxxxxxx

}

public class BinarySearch {

​

  public static int binarySearch(int[] arr, int target) {

    return binarySearch(arr, target, 0, arr.length - 1);

  }

​

  private static int binarySearch(int[] arr, int target, int start, int end) {

    if (start > end) {

      return -1;

    }

​

    int mid = start + (end - start) / 2;

​

    if (arr[mid] == target) {

      return mid;

    } else if (arr[mid] < target) {

      return binarySearch(arr, target, mid + 1, end);

    } else {

      return binarySearch(arr, target, start, mid - 1);

    }

  }

​

  public static void main(String[] args) {

    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    int target = 5;

    int index = binarySearch(arr, target);

    System.out.println("Target " + target + " found at index: " + index);

  }

​

Merge Sort

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer approach. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves to produce the final sorted output.

The algorithm consists of two main steps: the splitting step and the merging step.

Splitting Step

In the splitting step, the algorithm repeatedly divides the input array into two halves until the size of each subarray becomes 1 or 0. This can be done by finding the midpoint of the array and recursively splitting the array into two parts: the left subarray and the right subarray.

Merging Step

In the merging step, the algorithm merges the two sorted subarrays into a single sorted array. It compares the elements from the two subarrays and inserts them into the resulting array in sorted order. This process is repeated until all the elements from both subarrays have been merged.

Here's an example implementation of the Merge Sort algorithm in Java:

{{code}}

The merge function merges two sorted subarrays: arr[l..m] and arr[m+1..r]. It first copies the elements from the subarrays to temporary arrays L and R, and then merges the elements back into the original array arr in sorted order.

The mergeSort function is the main driver function that recursively sorts the input array. It calls itself to sort the left and right halves of the array, and then merges the sorted halves using the merge function.

Try running the example code to see Merge Sort in action. It sorts the array [5, 2, 8, 12, 1, 7] and prints the sorted array [1, 2, 5, 7, 8, 12].

xxxxxxxxxx

}

// Merge two subarrays of arr[]

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r) {

    // Calculate sizes of two subarrays

    int n1 = m - l + 1;

    int n2 = r - m;

​

    // Create temporary arrays

    int L[] = new int [n1];

    int R[] = new int [n2];

​

    // Copy data to temporary arrays

    for (int i=0; i<n1; ++i)

        L[i] = arr[l + i];

    for (int j=0; j<n2; ++j)

        R[j] = arr[m + 1+ j];

​

    // Merge the temporary arrays

​

    // Initial indexes of first and second subarrays

    int i = 0, j = 0;

​

    // Initial index of merged subarray array

    int k = l;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

Tree Traversal

Tree traversal is the process of visiting each node in a tree data structure in a specific order. It allows us to access the data stored in each node of the tree.

There are three main types of tree traversal: in-order traversal, pre-order traversal, and post-order traversal.

In-order Traversal

In in-order traversal, the left subtree is visited first, followed by the root node, and then the right subtree. It produces sorted output when applied to a binary search tree (BST).

Here's the recursive implementation of in-order traversal in Java:

{{code}}

The inOrderTraversal function takes a tree node as input and performs in-order traversal by recursively traversing the left subtree, visiting the root node, and then recursively traversing the right subtree. The data of each visited node is printed.

Pre-order Traversal

In pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree. It is useful for creating a copy of the tree.

Post-order Traversal

In post-order traversal, the left subtree is visited first, followed by the right subtree, and then the root node. It is useful for deleting the nodes of a tree.

Try implementing and running the in-order traversal function on a binary tree to see the order in which the nodes are visited and their corresponding data.

xxxxxxxxxx

// Binary Tree Node

class Node {

    int data;

    Node left, right;

​

    public Node(int item) {

        data = item;

        left = right = null;

    }

}

​

// In-order traversal

void inOrderTraversal(Node node) {

    if (node != null) {

        inOrderTraversal(node.left);

        System.out.print(node.data + " ");

        inOrderTraversal(node.right);

    }

}