Recursion — AP Computer Science A Practice Worksheet

Grades 10–12 Hard difficulty 10 problems

Recursion is when a method calls itself to solve a smaller instance of the same problem. Every recursive function needs a base case (stopping condition) and a recursive case that progresses toward the base.

Classic examples: factorial(n) = n × factorial(n−1) with base factorial(0) = 1; Fibonacci fib(n) = fib(n−1) + fib(n−2) with bases fib(0)=0, fib(1)=1.

Each recursive call adds a stack frame. Without a base case, you get stack overflow. Tracing requires tracking call stack depth and return values unwinding.

Skills practiced

  • Identifying base and recursive cases
  • Tracing recursive method calls
  • Writing simple recursive functions
  • Understanding call stack behavior
Name: Date: Period:

Practice Worksheet: Recursion

Instructions: Solve each problem carefully. Show all work clearly. Write your final answer in the space provided or on a separate sheet as directed.

  1. 1.**Multiple Choice:** Consider the following recursive method: “` public static int mystery(int n) { if (n <= 0) return 0; return n + mystery(n - 2); } “` What is the value of `mystery(7)`? (A) 12 (B) 16 (C) 20 (D) 24 (E) 28
    1. A. 12
    2. B. 16
    3. C. 20
    4. D. 24
    5. E. 28
  2. 2.**Free Response:** Write a recursive method `int sumDigits(int n)` that returns the sum of the digits of a non-negative integer `n`. For example, `sumDigits(123)` should return 1+2+3=61+2+3=6. Assume `n` is non-negative. Show your method below.
  3. 3.**Short Answer:** The following recursive method is intended to compute xnx^n for integer n≥0n \ge 0: “` public static double power(double x, int n) { if (n == 0) return 1; return x * power(x, n - 1); } “` How many recursive calls are made when computing `power(2, 5)`? (Do not count the initial call.)
  4. 4.**Multiple Choice:** What does the following recursive method return for `foo(5)`? “` public static int foo(int n) { if (n < 2) return n; return foo(n - 1) + foo(n - 2); } “` (A) 3 (B) 5 (C) 8 (D) 13 (E) 21
    1. A. 3
    2. B. 5
    3. C. 8
    4. D. 13
    5. E. 21
  5. 5.**Free Response:** Write a recursive method `boolean isPalindrome(String s)` that returns `true` if the string `s` is a palindrome (reads the same forward and backward), and `false` otherwise. Ignore case. You may assume the string contains only letters. Show your method below.
  6. 6.**Short Answer:** Consider the recursive method: “` public static int g(int n) { if (n < 10) return n; return g(n / 10) + n } “` What is the value of `g(9876)`?
  7. 7.**Multiple Choice:** How many times is the recursive method called (including the initial call) when evaluating `h(4)`? “` public static int h(int n) { if (n <= 1) return 1; return h(n - 1) + h(n - 2); } “` (A) 5 (B) 7 (C) 9 (D) 11 (E) 13
    1. A. 5
    2. B. 7
    3. C. 9
    4. D. 11
    5. E. 13
  8. 8.**Free Response:** Write a recursive method `void printReverse(String s)` that prints the string `s` in reverse order. For example, `printReverse("hello")` should print `"olleh"`. Show your method below.
  9. 9.**Short Answer:** The following recursive method is intended to compute the greatest common divisor (GCD) of two positive integers using Euclid's algorithm: “` public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a } “` What is the value of `gcd(48, 18)`?
  10. 10.**Multiple Choice:** What is the output of the following code? “` public static void main(String[] args) { System.out.println(quiz(4)); } public static int quiz(int n) { if (n == 0) return 0; return n + quiz(n - 1); } “` (A) 6 (B) 8 (C) 10 (D) 12 (E) 14
    1. A. 6
    2. B. 8
    3. C. 10
    4. D. 12
    5. E. 14

Answer Key

  1. 1.
    `mystery(7) = 7 + mystery(5) = 7 + 5 + mystery(3) = 7 + 5 + 3 + mystery(1) = 7 + 5 + 3 + 1 + mystery(-1) = 7 + 5 + 3 + 1 + 0 = 16`.
    Final answer: B (16)
  2. 2.
    Final answer: “` public static int sumDigits(int n) { if (n < 10) return n; return n } “`
  3. 3.
    `power(2,5)` calls `power(2,4)`, which calls `power(2,3)`, which calls `power(2,2)`, which calls `power(2,1)`, which calls `power(2,0)`. That is 5 recursive calls.
    Final answer: 5
  4. 4.
    `foo(5) = foo(4) + foo(3) = (foo(3)+foo(2)) + (foo(2)+foo(1)) = ((foo(2)+foo(1))+(foo(1)+foo(0))) + ((foo(1)+foo(0))+1) = ((1+1)+1+0)+(1+0+1) = 5`.
    Final answer: B (5)
  5. 5.
    Final answer: “` public static boolean isPalindrome(String s) { if (s.length() <= 1) return true; if (s.charAt(0) != s.charAt(s.length()-1)) return false; return isPalindrome(s.substring(1, s.length()-1)); } “`
  6. 6.
    `g(9876) = g(987) + 6 = (g(98) + 7) + 6 = ((g(9) + 8) + 7) + 6 = (9 + 8) + 7 + 6 = 30`.
    Final answer: 30
  7. 7.
    `h(4)` calls `h(3)` and `h(2)`. `h(3)` calls `h(2)` and `h(1)`. `h(2)` calls `h(1)` and `h(0)`. `h(1)` and `h(0)` are base cases. Total calls: `h(4)`, `h(3)`, `h(2)` (twice), `h(1)` (three times), `h(0)` (once) = 1+1+2+3+1 = 8? Wait, recount: `h(4)` (1), `h(3)` (2), `h(2)` from `h(4)` (3), `h(2)` from `h(3)` (4), `h(1)` from `h(3)` (5), `h(1)` from first `h(2)` (6), `h(0)` from first `h(2)` (7), `h(1)` from second `h(2)` (8), `h(0)` from second `h(2)` (9). So 9 calls.
    Final answer: C (9)
  8. 8.
    Final answer: “` public static void printReverse(String s) { if (s.length() == 0) return; printReverse(s.substring(1)); System.out.print(s.charAt(0)); } “`
  9. 9.
    `gcd(48,18) = gcd(18, 48
    Final answer: 6
  10. 10.
    `quiz(4) = 4 + quiz(3) = 4 + 3 + quiz(2) = 4 + 3 + 2 + quiz(1) = 4 + 3 + 2 + 1 + quiz(0) = 4 + 3 + 2 + 1 + 0 = 10`.
    Final answer: C (10)
Download PDF

Common mistakes to avoid

  • Missing or incorrect base case
  • Recursive case not moving toward base case
  • Confusing recurrence relation with loop
  • Exponential redundancy in naive Fibonacci without memoization

Generate your own like this

Want a fresh set of recursion problems at your chosen difficulty? Use WorksheetSmith to compile a custom, print-ready PDF in seconds.

Generate a custom Recursion worksheet

Related worksheets

Last updated: 2026

Open the WorksheetSmith worksheet app