Unit 10: Recursion

This unit explores recursion in Java, a powerful programming technique where a method calls itself to solve complex problems by breaking them down into simpler subproblems.

Key Concepts

  • Recursion: A method that calls itself to solve a problem.
  • Base Case: The condition that stops the recursion.
  • Recursive Case: The part where the method calls itself with a modified parameter.
  • Stack Overflow: Occurs when recursion goes too deep without reaching a base case.
  • Tail Recursion: A recursive call that is the last operation in the method.
  • Recursive vs. Iterative: Understanding when to use each approach.
  • Binary Search: A recursive algorithm for searching sorted arrays.
  • Merge Sort: A recursive sorting algorithm.
  • Factorial: A classic example of recursion.
  • Fibonacci Sequence: Another common recursive problem.

Example Code


// Example: Recursion in Java
public class RecursionExample {
    // Factorial using recursion
    public static int factorial(int n) {
        if (n <= 1) {
            return 1;  // Base case
        }
        return n * factorial(n - 1);  // Recursive case
    }
    
    // Fibonacci sequence using recursion
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;  // Base case
        }
        return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive case
    }
    
    public static void main(String[] args) {
        System.out.println("Factorial of 5: " + factorial(5));
        System.out.println("Fibonacci(6): " + fibonacci(6));
    }
}

Interactive Code Playground

Try out your own recursive code here!

Output:
Note: This is a simulated environment. For actual Java code execution, please use an IDE or online Java compiler.

For actual code execution, we recommend using:

Multiple Choice Quiz

Question 1: Base Case

What is the purpose of a base case in recursion?

To stop the recursive calls and return a value
To make the recursive function more complex
To increase the number of recursive calls
To skip some recursive calls
The correct answer is A. The base case provides a stopping condition for the recursion, preventing infinite recursive calls and allowing the function to return a value.
Question 2: Recursive Case

What is the recursive case in a recursive function?

The part that calls the function again with a smaller problem
The part that handles the base case
The part that prints the result
The part that initializes variables
The correct answer is A. The recursive case breaks down the problem into smaller subproblems and calls the function again with these smaller problems.
Question 3: Stack Overflow

What happens if a recursive function doesn't have a proper base case?

It causes a stack overflow error
It runs faster
It returns the wrong answer
It skips some calculations
The correct answer is A. Without a proper base case, the recursive function will keep calling itself indefinitely until the call stack is full, resulting in a stack overflow error.

Practice Problems

  1. Implement a recursive method to calculate the power of a number (x^n).
  2. Write a recursive method to find the greatest common divisor (GCD) of two numbers.
  3. Create a recursive method to check if a string is a palindrome.
  4. Implement a recursive method to generate all possible combinations of a string.
  5. Write a recursive method to solve the N-Queens problem.

Tips for Success

  • Always identify the base case(s) first: These are the conditions that stop the recursion.
  • Make sure the recursive case moves toward the base case: Each recursive call should reduce the problem size.
  • Consider using iteration instead of recursion when the problem is simple or when stack overflow is a concern.
  • Use recursion for problems that naturally break down into smaller subproblems.
  • Be careful with multiple recursive calls: They can lead to exponential time complexity.
  • Consider using memoization to optimize recursive solutions with overlapping subproblems.
  • Test your recursive methods with edge cases and small inputs first.
← Previous Unit: Inheritance
Back to Unit 1 →