Advanced Java · Week 7

Recursion

Step 1 of 8

Java 2 Guided Tutorials - Week 7: Recursion

What You'll Learn

Welcome to Week 7 of Java 2! This week, we'll explore recursion, a powerful programming concept where a function calls itself to solve a problem. Recursion can lead to elegant solutions for complex problems and is fundamental in many algorithms.

                    Lesson Overview:
                    Understanding Recursion
Basic Recursive Functions
Recursive vs Iterative Approaches
Tail Recursion
Recursion in Problem Solving
Quiz to test your knowledge
Weekly project to apply what you've learned

                

By the end of this week, you'll have a solid understanding of recursion and how to apply it in your Java programs. Let's dive in!

1. Understanding Recursion

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It's a way of breaking down a complex problem into smaller, more manageable subproblems. Each recursive call works on a smaller instance of the same problem, eventually reaching a base case that can be solved directly.

                    Key Components of Recursion:
                    Base Case: The condition that stops the recursion
Recursive Case: The part where the function calls itself
Progress Towards Base Case: Each recursive call should move closer to the base case

                

Here's a simple example to illustrate recursion:

public class RecursionExample {
    public static void countDown(int n) {
        // Base case
        if (n == 0) {
            System.out.println("Done!");
            return;
        }
        
        // Print the current number
        System.out.println(n);
        
        // Recursive case
        countDown(n - 1);
    }

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

In this example, the countDown function calls itself with a smaller number each time, until it reaches zero (the base case). Try running this code and observe how recursion works step by step.

Write your code here

Make it print 5 4 3 2 1 Done!

Did it work?

Your program should print this:

5
4
3
2
1
Done!

Paste what you got:

2. Basic Recursive Functions

Common Recursive Functions

Let's explore some basic recursive functions to help you understand how recursion works in practice. We'll look at factorial calculation and the Fibonacci sequence, two classic examples of recursion.

Factorial Calculation

The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n. Here's a recursive implementation:

public class FactorialExample {
    public static int factorial(int n) {
        // Base case
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // Recursive case
        return n * factorial(n - 1);
    }

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

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. Here's a recursive implementation to find the nth Fibonacci number:

public class FibonacciExample {
    public static int fibonacci(int n) {
        // Base cases
        if (n <= 1) {
            return n;
        }
        
        // Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("8th Fibonacci number: " + fibonacci(8));
    }
}

Try running these examples and experiment with different input values. Can you trace the recursive calls for small inputs?

Write your code here

Make it print Factorial of 5: 120 8th Fibonacci number: 21

Did it work?

Your program should print this:

Factorial of 5: 120
8th Fibonacci number: 21

Paste what you got:

3. Recursive vs Iterative Approaches

Comparing Recursion and Iteration

Many problems can be solved using either recursive or iterative approaches. Let's compare these two methods to understand their strengths and weaknesses.

                    Recursion vs Iteration:
                    Recursion can lead to more elegant and readable code for some problems
Iteration is often more efficient in terms of memory usage
Recursive solutions can be slower due to function call overhead
Some problems are naturally recursive and harder to solve iteratively

                

Let's look at an example of calculating the sum of numbers from 1 to n using both approaches:

public class SumExample {
    // Recursive approach
    public static int sumRecursive(int n) {
        if (n <= 1) {
            return n;
        }
        return n + sumRecursive(n - 1);
    }

    // Iterative approach
    public static int sumIterative(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Recursive sum: " + sumRecursive(n));
        System.out.println("Iterative sum: " + sumIterative(n));
    }
}

Both approaches produce the same result, but they differ in how they achieve it. The recursive approach breaks down the problem into smaller subproblems, while the iterative approach uses a loop to accumulate the sum. Try implementing both approaches for other problems, like factorial or Fibonacci, and compare their performance for larger inputs.

Write your code here

Make it print Recursive sum: 15 Iterative sum: 15

Did it work?

Your program should print this:

Recursive sum: 15
Iterative sum: 15

Paste what you got:

4. Tail Recursion

Understanding Tail Recursion

Tail recursion is a special form of recursion where the recursive call is the last operation in the function. This allows for potential optimizations by the compiler, as it can transform the recursion into a loop, saving stack space.

                    Key Points:
                    The recursive call is the last operation in the function
No computation is done after the recursive call
Can be optimized by the compiler to use constant stack space
Not all recursive functions can be easily converted to tail recursive form

                

Here's an example of converting the factorial function to use tail recursion:

public class TailRecursionExample {
    // Non-tail recursive factorial
    public static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    // Tail recursive factorial
    public static int factorialTail(int n, int accumulator) {
        if (n <= 1) return accumulator;
        return factorialTail(n - 1, n * accumulator);
    }

    public static void main(String[] args) {
        System.out.println("Non-tail recursive: " + factorial(5));
        System.out.println("Tail recursive: " + factorialTail(5, 1));
    }
}

In the tail recursive version, we use an accumulator to store intermediate results. This allows the function to return immediately after the recursive call, without needing to perform any additional computations. While Java doesn't automatically optimize tail recursion, understanding this concept can help you write more efficient recursive functions.

Write your code here

Make it print Non-tail recursive: 120 Tail recursive: 120

Did it work?

Your program should print this:

Non-tail recursive: 120
Tail recursive: 120

Paste what you got:

5. Recursion in Problem Solving

Applying Recursion to Solve Problems

Recursion is particularly useful for solving problems that have a recursive structure or can be broken down into smaller, similar subproblems. Let's look at a classic example: the Tower of Hanoi puzzle.

Tower of Hanoi:

The puzzle consists of three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. The objective is to move the entire stack to another rod, obeying the following rules:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
No larger disk may be placed on top of a smaller disk.

Here's a recursive solution to the Tower of Hanoi problem:

public class TowerOfHanoi {
    public static void solveTowerOfHanoi(int n, char source, char auxiliary, char destination) {
        // Base case: If only one disk, move it directly
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        
        // Move n-1 disks from source to auxiliary using destination as auxiliary
        solveTowerOfHanoi(n - 1, source, destination, auxiliary);
        
        // Move the nth disk from source to destination
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        
        // Move n-1 disks from auxiliary to destination using source as auxiliary
        solveTowerOfHanoi(n - 1, auxiliary, source, destination);
    }

    public static void main(String[] args) {
        int numberOfDisks = 3;
        solveTowerOfHanoi(numberOfDisks, 'A', 'B', 'C');
    }
}

This recursive solution breaks down the problem into smaller subproblems, moving n-1 disks recursively. Try running this code and observe how it solves the Tower of Hanoi puzzle step by step. Can you visualize the process for a small number of disks?

Write your code here

Make it print Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C

Did it work?

Your program should print this:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Paste what you got:

Quick check

1. What is the base case in a recursive function?
2. What is tail recursion?
3. Which of the following is NOT a common use case for recursion?

7. Weekly Project: Recursive File Explorer

Project Description

For this week's project, you'll create a simple recursive file explorer that lists all files and directories in a given directory and its subdirectories.

                    Requirements:
                    Create a recursive function that explores directories
Print the names of all files and directories
Show the directory structure with proper indentation
Handle potential exceptions (e.g., access denied to certain directories)
Implement a simple command-line interface to specify the starting directory

                

Here's a template to get you started:

import java.io.File;
import java.util.Scanner;

public class RecursiveFileExplorer {
    public static void exploreDirectory(File directory, String indent) {
        // TODO: Implement the recursive file exploration
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the directory path to explore: ");
        String path = scanner.nextLine();
        
        File rootDirectory = new File(path);
        if (rootDirectory.exists() && rootDirectory.isDirectory()) {
            System.out.println("Exploring directory: " + rootDirectory.getAbsolutePath());
            exploreDirectory(rootDirectory, "");
        } else {
            System.out.println("Invalid directory path.");
        }
    }
}

Implement the exploreDirectory method using recursion to list all files and subdirectories. Use proper indentation to show the directory structure. Remember to handle exceptions and edge cases. Once you've completed the implementation, test your file explorer with different directories and ensure it correctly displays the file structure.

Write your code here

Make it print Exploring directory: /path/to/directory - File1.txt - Folder1 - Subfolder - File2.txt - File3.txt - File4.txt

Did it work?

Your program should print this:

Exploring directory: /path/to/directory
- File1.txt
- Folder1
  - Subfolder
    - File2.txt
  - File3.txt
- File4.txt

Paste what you got:

PreviousLists NextTest