Home of real teaching & learning
  • Full support for teachers
  • Focus on critical thinking
  • Engaging classroom activities
  • Integrated student eBook
  • Assessed tasks / qBank
  • Practice exam questions
Find out more Download brochure

The InThinking Guarantee: Our sites are written by expert practitioners and not by AI

See our AI policy

Disclaimer: InThinking subject sites are neither endorsed by nor connected with the International Baccalaureate Organisation.

Don't miss out, find out!

B 2.4.4 Recursion Java (HL Only)

B 2.4.4 Explain the fundamental concept of recursion and its applications in programming. (HL only)

Unlock the power of recursion! This section explores the fascinating world of recursive programming. Learn how functions can call themselves to solve problems, discover the advantages and limitations of this technique, and see how it's applied in real-world scenarios.

Introduction

Recursion is a powerful and elegant programming technique that allows you to solve problems by breaking them down into smaller, self-similar subproblems. In this chapter, we'll explore the fundamentals of recursion, its advantages, disadvantages, and applications in Java.

What is Recursion?

Recursion is a technique where a function calls itself to solve a problem. It's like a set of Russian nesting dolls, each containing a smaller version of itself. The key components of a recursive function are:

Base Case: The condition that stops the recursion. It's like the smallest doll that doesn't contain any others. Without a base case, the recursion would continue infinitely, leading to a stack overflow error.
Recursive Case: The step where the function calls itself with a smaller subproblem. It's like opening a doll to reveal a smaller one. The recursive case must eventually lead to the base case to ensure the recursion terminates.

Simple Example: Factorial

Let's illustrate recursion with a classic example: calculating the factorial of a number. The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 * 4 * 3 * 2 * 1 1  = 120.   

Here's the recursive Java code to calculate the factorial:

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);
    }
}

Let's trace the execution of factorial(4):

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1 (base case)


Now, the values are returned back up the chain: factorial(1) = 1 * 1 = 1 factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24

Advantages of Recursion

Code Readability: Recursion can make code more concise and easier to understand, especially for problems with repetitive structures. The recursive solution often closely mirrors the problem's definition, making the code more intuitive.
Elegance: Recursion can provide elegant solutions for problems with inherent recursive structures, such as tree traversal, fractal generation, and divide-and-conquer algorithms.

Disadvantages of Recursion

Stack Overflow: Each recursive call adds a new frame to the call stack. Excessive recursion can exhaust the stack memory, leading to stack overflow errors and crashing the program.
Performance: Recursive function calls can have overhead in terms of time and memory compared to iterative solutions. This overhead can be significant for deep recursion or problems with simple recursive structures that can be easily converted to loops.

Applications of Recursion

Quicksort: A divide-and-conquer sorting algorithm that uses recursion to partition the data around a pivot and sort the subpartitions.

How Quicksort  works

Quicksort: A Recursive Divide-and-Conquer Algorithm

Quicksort is an efficient sorting algorithm that uses a divide-and-conquer strategy, making it naturally suited for a recursive implementation. The core idea is to break a large sorting problem down into two smaller, independent sorting problems<

Key Steps in Quicksort

The Quicksort algorithm involves three main steps, two of which are executed recursively:

  1. Choose a Pivot: Select an element to act as the pivot. On this page we always use the last element of the list. This is a fixed rule, so the same method works on the whole list and on every sub-list the recursion produces. Other versions of quicksort take the first element, the middle element or a random one. The sorting still works; only the speed changes.
  2. Partition: Rearrange the elements in the list so that all elements less than or equal to the pivot are to its left, and all elements greater than the pivot are to its right. After this step, the pivot is in its final sorted position.
  3. Recursively Sort Sub-lists: Recursively apply the quicksort algorithm to the sub-list of elements to the left of the pivot and the sub-list to the right of the pivot.

The base case (the condition that stops the recursion) is reached when a sub-list contains zero or one element, as such a list is already sorted

The pivot is placed, then it stays put

The pivot is the value every other element is compared against. Partitioning moves the smaller values to its left and the larger values to its right, which puts the pivot in its final sorted position. It never moves again.

This is why the two sub-lists are smaller sub-problems. Each holds one fewer element than before, and neither contains the pivot. The recursion only has to sort what is to the left of the pivot and what is to the right.

KEY IDEA The pivot is chosen by a rule, not by searching for a good value. Here the rule is "take the last element". Once partitioning is done the pivot is in its final place, so the recursion is left with two shorter lists to sort.

Why the pivot choice matters

A good pivot splits the list into two parts of roughly equal size. The recursion then roughly halves the work at each level, and quicksort sorts n elements in about n log n steps.

A poor pivot splits off almost nothing. If the pivot is always the smallest or the largest value, one side is empty and the other holds everything except the pivot. The recursion then goes n levels deep and quicksort slows to about n² steps.

The "last element" rule meets this worst case on a list that is already sorted, because the last element is then always the largest value left. This is the link back to the limitations of recursion: an unbalanced split means deeper recursion, more stack frames and more work.

Step-by-Step Example

Let's trace the quicksort process on a small array: 

Initial Array:

[4, 3, 1, 2, 6, 9, 7, 10, 5]

1. First Partition (Divide)
  • Choose Pivot: We select the element 5 as the pivot.
  • Partition: We rearrange the array so elements ≤5 are on the left and elements ≥ 5 are on the right.
    • The numbers 4, 3, 1, 2 are less than 5.
    • The numbers 9, 7, 10, 6 are greater than 5.

The array is now divided into two sub-problems, with the pivot 5 correctly placed:

(Sub-list 1) (Pivot) (Sub-list 2)

[4, 3, 1, 2]     5     [6, 9, 7, 10]

2. Recursive Call on Sub-list 1: [4, 3, 1, 2]
  • Choose Pivot: We select 2 as the pivot for this sub-list.
  • Partition: Elements ≤2 on the left, elements ≥2 on the right.
    • Elements ≤2: [1]
    • Elements ≥2: [4, 3]

The first sub-list is further divided:

(Sub-list 1A) (Pivot) (Sub-list 1B)

[1]     2     [4, 3]

3. Further Recursion (Conquer)

This process continues recursively until all sub-lists are trivially sorted (i.e., contain only one element)

  • Sub-list 1A: [1]
    • Base Case: Contains 1 element. It is sorted.
  • Sub-list 1B: [4, 3]
    • Choose Pivot: Select 3.
    • Partition: Elements ≤3: [] / Elements ≥3: [4]
    • Result: 3 [4]. Now sort [4].
    • Base Case: [4] is sorted.
  • Sub-list 2: [6, 9, 7, 10]
    • A full trace would break this down and continues until all elements are positioned correctly.

The final result after all recursive calls return is the complete sorted list:

[1, 2, 3, 4, 5, 6, 7, 9, 10]

This hierarchical breaking down of the problem demonstrates the recursive nature of quicksort.

Recursive call tree

quickSort([4, 3, 1, 2, 6, 9, 7, 10, 5])   pivot 5
├── quickSort([4, 3, 1, 2])               pivot 2
│   ├── quickSort([1])                     base case
│   └── quickSort([4, 3])                 pivot 3
│       ├── quickSort([])                   base case
│       └── quickSort([4])                  base case
└── quickSort([6, 9, 7, 10])              pivot 10
    ├── quickSort([6, 9, 7])              pivot 7
    │   ├── quickSort([6])                 base case
    │   └── quickSort([9])                 base case
    └── quickSort([])                      base case

Each box is one call to quickSort. A call either meets the base case and returns, or partitions its list and makes two more calls. Read top to bottom, the problem is broken into smaller pieces. Read bottom to top, the sorted pieces return and join back together.

Where the recursion is in quicksort

Quicksort has the same two parts as any recursive method.

Base case: a sub-list with zero or one element. A list that short is already sorted, so the call does nothing and returns.

Recursive case: a sub-list with two or more elements. Choose the pivot, partition, then call quicksort again on the left sub-list and on the right sub-list.

Partitioning is not recursive. It is a single pass that places the pivot and separates the smaller and larger values. The recursion is the two calls that run after it, one for each side of the pivot.

In the code this is the line if (low < high). When low is no longer less than high, the sub-list holds one element or none, the base case is met, and that branch stops calling itself. The two quickSort(...) calls inside the if are the recursive case.

COMMON EXAM MISTAKE
Students often say the partition step is the recursion. It is not. Partition is one pass through the sub-list. The recursion is the two quicksort calls that run after it, one on each side of the pivot.

Quicksort code

public class QuickSort {
    /**
     * The main recursive method that sorts the array segment a[low..high].
     * Base Case: When low is no longer less than high (0 or 1 element), the segment is sorted.
     * @param arr The array to be sorted.
     * @param low The starting index of the sub-array.
     * @param high The ending index of the sub-array.
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pivotIndex = partition(arr, low, high);
            // Recursively sort the sub-arrays before and after the pivot
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    /**
     * Partitions the array segment around the pivot element (chosen as arr[high]).
     * @param arr The array to be partitioned.
     * @param low The starting index.
     * @param high The ending index and pivot position.
     * @return The final index of the pivot element.
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Select the rightmost element as the pivot
        int i = (low - 1);      // Pointer for the greater element
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Swap the pivot (arr[high]) with the element at the correct pivot position (i + 1)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

Merge Sort: Another divide-and-conquer sorting algorithm that recursively splits the array, sorts the sub-arrays, and merges them.
Tower of Hanoi: A classic puzzle that involves moving disks between pegs, which can be solved elegantly using a recursive algorithm.
Tree Traversal: Recursion is naturally suited for traversing tree structures like binary trees. Common tree traversal algorithms, such as inorder, preorder, and postorder traversal, are implemented recursively.
Fractal Generation: Fractals are self-similar patterns that can be generated using recursive algorithms. Examples include the Mandelbrot set and the Sierpinski triangle.

Limitations of Recursion

Stack Overflow: As mentioned earlier, deep recursion can lead to stack overflow errors. This is a major limitation, especially when dealing with problems requiring many recursive calls.
Performance: Recursive function calls can introduce overhead compared to iterative solutions. This overhead can be significant for deep recursion or problems with simple recursive structures that can be easily converted to loops.
Memory Usage: Recursion uses stack memory to store information about each function call, including local variables, parameters, and the return address. Excessive recursion can lead to high memory usage, potentially exceeding the available stack space.

When to Use Recursion

Suitable Problems: Recursion is ideal for problems that can be naturally broken down into smaller, self-similar subproblems. This often involves a divide-and-conquer approach.
Code Readability: If code readability and maintainability are priorities, and performance is not a critical concern, recursion can be a good choice.

Key Questions

Hinge Question: Explain how the base and recursive cases work together to ensure that a recursive function terminates.

Answer: The base case provides a condition for stopping the recursion. The recursive case makes a recursive call with a smaller subproblem, eventually leading to the base case. Without a base case, the recursion would continue infinitely.

Hinge Question: Describe a scenario where recursion might be less efficient than an iterative solution.

Answer: Recursion can be less efficient when the recursive structure is simple and easily converted to a loop. The overhead of function calls in recursion can add up, especially for deep recursion. For example, calculating the sum of a list might be more efficiently done with a loop than with recursion.

Hinge Question: In this page the pivot is always the last element. What kind of starting list would make quicksort slowest, and why?

A list that is already sorted, or sorted in reverse. The last element is then always the largest, or smallest, value, so each partition splits off only the pivot and leaves everything else on one side. The recursion goes as deep as the number of elements, and quicksort slows to about n² steps.

Hinge Question:  Why is it important to be mindful of the potential for stack overflow errors when using recursion?

Answer: Stack overflow errors occur when the call stack exceeds its capacity due to excessive recursion. This can lead to program crashes and unexpected behaviour. Therefore, it's crucial to design recursive algorithms carefully, considering the depth of recursion and the size of the input data.

All materials on this website are for the exclusive use of teachers and students at subscribing schools for the period of their subscription. Any unauthorised copying or posting of materials on other websites is an infringement of our copyright and could result in your account being blocked and legal action being taken against you.

Help