Back

Activity 5.12 — Recursion

divider

Introduction

Activity 5.12

Introduction to Recursion

What is recursion?

// What is recursion?
// A method that calls itself.


public static void greet(int n)
{
    if (n <= 0)
    {
        return; // base case
    }


    System.out.println("Hello");
    greet(n - 1); // recursive call
}

Two Required Parts

// Every recursive method needs:
// 1) Base case (stopping condition)
// 2) Recursive case (smaller problem)


if (n <= 0)   // base case
{
    return;
}


return n + sum(n - 1); // recursive case

Thinking Recursively

// Think of recursion like:
// "Solve a smaller version of the same problem."


sum(4)
= 4 + sum(3)
= 4 + 3 + sum(2)
= 4 + 3 + 2 + sum(1)
= 4 + 3 + 2 + 1

Without a Base Case?

// What happens without a base case?


public static void bad()
{
    bad(); // infinite recursion
}


// This causes a StackOverflowError.

Recursion with Arrays

// Recursive array processing idea
// Instead of using a loop,
// move through the array using an index.


sum(arr, index)
{
    if (index == arr.length)
        return 0;


    return arr[index] + sum(arr, index + 1);
}

Today's Goals

  • Understand base vs recursive case.
  • Trace recursive calls.
  • Write simple recursive methods.
  • Apply recursion to arrays.

'F' → Fullscreen

Objectives

  • icon Explain the structure of a recursive method.
  • icon Trace recursive calls step-by-step.
  • icon Write simple recursive numeric methods.
  • icon Write recursive methods that process arrays.
divider

Activity Tasks

  • icon Create a project named Activity5_12_Recursion.
  • icon Complete Tasks 1-4.
  • icon Test with multiple inputs.

Figures: Reference Examples

Figure 1 — Factorial
// Figure 1 — Factorial
public static int factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }


    return n * factorial(n - 1);
}
Figure 2 — Sum 1 to n
// Figure 2 — Sum from 1 to n
public static int sum(int n)
{
    if (n == 0)
    {
        return 0;
    }


    return n + sum(n - 1);
}
Figure 3 — Recursive Array Sum
// Figure 3 — Recursive array sum
public static int sumArray(int[] arr, int index)
{
    if (index == arr.length)
    {
        return 0;
    }


    return arr[index] + sumArray(arr, index + 1);
}
Figure 4 — Recursive Search
// Figure 4 — Recursive linear search
public static int search(int[] arr, int target, int index)
{
    if (index == arr.length)
    {
        return -1;
    }


    if (arr[index] == target)
    {
        return index;
    }


    return search(arr, target, index + 1);
}

Task 1: Recursive Countdown

Task 1 — Countdown
// Task 1 — Write a Recursive Countdown
//
// Write a method:
// countdown(int n)
//
// It should print numbers from n down to 1.
// Use recursion.
// If n is 0 or less, stop.


public class Program
{
    public static void main(String[] args)
    {
        countdown(5);
    }


    public static void countdown(int n)
    {
        // Write your code here
    }
}

Task 2: Recursive Power

Task 2 — Power
// Task 2 — Recursive Power
//
// Write a method:
// power(int base, int exponent)
//
// Example:
// power(2, 3) should return 8.
//
// Hint:
// base^0 = 1


public class Program
{
    public static void main(String[] args)
    {
        System.out.println(power(2, 3));
    }


    public static int power(int base, int exponent)
    {
        // Write your code here
        return 0;
    }
}

Task 3: Recursive Array Max

Task 3 — Max in Array
// Task 3 — Recursive Array Max
//
// Write a method:
// max(int[] arr, int index)
//
// It should return the largest value in the array.
// Start by calling: max(arr, 0)
//
// Hint:
// Base case: index == arr.length - 1


public class Program
{
    public static void main(String[] args)
    {
        int[] nums = {4, 7, 2, 9, 5};
        System.out.println(max(nums, 0));
    }


    public static int max(int[] arr, int index)
    {
        // Write your code here
        return 0;
    }
}

Task 4: Recursive Search

Task 4 — Contains
// Task 4 — Recursive Search
//
// Write a recursive method that returns
// true if a target exists in the array.
//
// Method:
// contains(int[] arr, int target, int index)
//
// Start with index = 0


public class Program
{
    public static void main(String[] args)
    {
        int[] nums = {3, 8, 1, 6, 9};


        System.out.println(contains(nums, 6, 0)); // true
        System.out.println(contains(nums, 5, 0)); // false
    }


    public static boolean contains(int[] arr, int target, int index)
    {
        // Write your code here
        return false;
    }
}
divider

Sample Output

Sample Output
Hello
Hello
Hello
Hello
Hello


120


10


9


true
false
divider

Reflection Questions

  1. What is the base case in a recursive method?
  2. What happens if you forget the base case?
  3. How is recursion similar to a loop?
  4. How is recursion different from a loop?
  5. When might recursion be clearer than iteration?
divider

Submission

Submit your completed activity.

Activity Complete