Back

Activity 5.13 — Recursion Practice

divider

Introduction

Activity 5.13

Recursion Practice and Tracing

Recursion Review

// Recursion review
// A recursive method has two parts:


// 1. Base case
// The stopping condition


// 2. Recursive case
// The method calls itself with a smaller problem

Example

// Example
public static int sum(int n)
{
    if (n == 0)
    {
        return 0;
    }


    return n + sum(n - 1);
}

Tracing Recursive Calls

// What does this return?


sum(4)


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

Every Call Moves Toward the Base Case

// Key idea
// Each recursive call moves closer
// to the base case.


sum(5)
sum(4)
sum(3)
sum(2)
sum(1)
sum(0)  <-- base case

Predict the Output

// Figure 1 — Predict the output


public static void mystery(int n)
{
    if (n == 0)
    {
        return;
    }


    System.out.println(n);
    mystery(n - 1);
}

Predict the Return Value

// Figure 2 — Predict the return value


public static int mystery(int n)
{
    if (n == 1)
    {
        return 1;
    }


    return n * mystery(n - 1);
}

Recursion with Strings

// Figure 3 — Recursive string length


public static int length(String s)
{
    if (s.equals(""))
    {
        return 0;
    }


    return 1 + length(s.substring(1));
}

Recursion with Arrays

// Figure 4 — Check if array is sorted


public static boolean isSorted(int[] arr, int index)
{
    if (index >= arr.length - 1)
    {
        return true;
    }


    if (arr[index] > arr[index + 1])
    {
        return false;
    }


    return isSorted(arr, index + 1);
}

'F' → Fullscreen

Objectives

  • icon Trace recursive method calls.
  • icon Predict the output of recursive programs.
  • icon Write recursive methods for numbers, strings, and arrays.
  • icon Apply recursion to solve small algorithmic problems.
divider

Activity Tasks

  • icon Create a project named Activity5_13_RecursionPractice.
  • icon Complete Tasks 1–5.
  • icon Test your methods with multiple inputs.

Figures: Reference Examples

Predict Output
// Figure 1 — Predict the output


public static void mystery(int n)
{
    if (n == 0)
    {
        return;
    }


    System.out.println(n);
    mystery(n - 1);
}
Predict Return Value
// Figure 2 — Predict the return value


public static int mystery(int n)
{
    if (n == 1)
    {
        return 1;
    }


    return n * mystery(n - 1);
}
Recursive String Length
// Figure 3 — Recursive string length


public static int length(String s)
{
    if (s.equals(""))
    {
        return 0;
    }


    return 1 + length(s.substring(1));
}
Recursive Sorted Check
// Figure 4 — Check if array is sorted


public static boolean isSorted(int[] arr, int index)
{
    if (index >= arr.length - 1)
    {
        return true;
    }


    if (arr[index] > arr[index + 1])
    {
        return false;
    }


    return isSorted(arr, index + 1);
}

Task 1: Trace the Output

Task 1 — Trace
// Task 1 — Trace the Output
//
// What does this program print?
//
// mystery(4);


public static void mystery(int n)
{
    if (n == 0)
    {
        return;
    }


    mystery(n - 1);
    System.out.println(n);
}


// Write the output as comments.

Task 2: Sum of Digits

Task 2 — digitSum
// Task 2 — Sum of Digits
//
// Write a recursive method:
//
// digitSum(int n)
//
// Examples:
// digitSum(538) → 16
// digitSum(42) → 6
//
// Hint:
// last digit = n % 10
// remaining digits = n / 10


public class Program
{
    public static void main(String[] args)
    {
        System.out.println(digitSum(538));
    }


    public static int digitSum(int n)
    {
        // Write your code here
        return 0;
    }
}

Task 3: Reverse a String

Task 3 — reverse
// Task 3 — Reverse a String
//
// Write a recursive method:
//
// reverse(String s)
//
// Example:
// reverse("hello") → "olleh"


public class Program
{
    public static void main(String[] args)
    {
        System.out.println(reverse("hello"));
    }


    public static String reverse(String s)
    {
        // Write your code here
        return "";
    }
}

Task 4: Check if Sorted

Task 4 — isSorted
// Task 4 — Check if Array is Sorted
//
// Write a recursive method:
//
// isSorted(int[] arr, int index)
//
// It should return true if the array
// is sorted in ascending order.


public class Program
{
    public static void main(String[] args)
    {
        int[] a = {1, 3, 5, 7};
        int[] b = {2, 4, 3, 8};


        System.out.println(isSorted(a, 0));
        System.out.println(isSorted(b, 0));
    }


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

Task 5: Final Challenge

Task 5 — countVowels
// Task 5 — Final Challenge
//
// Write a recursive method:
//
// countVowels(String s)
//
// It should count how many vowels
// appear in the string.
//
// Example:
// countVowels("recursion") → 4


public class Program
{
    public static void main(String[] args)
    {
        System.out.println(countVowels("recursion"));
    }


    public static int countVowels(String s)
    {
        // Write your code here
        return 0;
    }
}
divider

Sample Output

Sample Output
1
2
3
4


16
olleh
true
false
4
divider

Reflection Questions

  1. Why does recursion always require a base case?
  2. How does recursion break a problem into smaller problems?
  3. What is one advantage of recursion compared to loops?
  4. What is one disadvantage of recursion?
  5. Which recursion problem today felt easiest to understand?
divider

Submission

Submit your completed activity.

Activity Complete