Computer Science · 12th Grade

Active learning ideas

Recursive Problem Solving Fundamentals

Recursion challenges students to visualize invisible processes, so active learning works because it turns abstract call stacks and return values into concrete, observable actions. When students physically act out the stack or diagram function calls, they build mental models that text explanations alone cannot provide.

• Common Core State Standards
• CSTA: 3B-AP-12
• CCSS.ELA-LITERACY.RST.11-12.3

• 20–35 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Simulation Game
• 20 min · Whole Class

Simulation Game: Human Recursion Stack

Assign students roles as function calls. The first student passes a problem card to the next student (a recursive call), and so on until the base case student solves it and returns the answer back up the chain. Students experience how each call waits for the next to return before it can proceed.

Explain how a complex problem can be defined by a smaller version of itself.

Facilitation Tip

During the Human Recursion Stack, have students stand in a line and call out their return values as they unwind the stack, ensuring they say their value before stepping back.

What to look for

Present students with a simple recursive function (e.g., a flawed factorial function). Ask them to trace its execution for n=3 on paper, identifying where it deviates from the correct logic or where a stack overflow might occur. Collect these traces for review.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 02

• Think-Pair-Share
• 25 min · Pairs

Think-Pair-Share: Base Case Detective

Present 5 recursive functions, some with missing or incorrect base cases. Students individually identify the flaw, then discuss with a partner before sharing with the class. The activity emphasizes that missing base cases cause infinite recursion.

Analyze the risks of using recursion regarding memory management and stack overflows.

Facilitation Tip

In the Base Case Detective activity, assign each pair a different recursive function snippet so they focus on identifying the base case first before debating the recursive step.

What to look for

Provide students with a problem description (e.g., summing elements in a list). Ask them to write down: 1. The base case. 2. The recursive step. 3. One potential risk of using recursion for this specific problem.

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

Activity 03

• Collaborative Problem-Solving
• 35 min · Small Groups

Problem Solving: Recursion Decomposition Workshop

Groups receive a list of problems such as summing a list, counting characters, or finding a file in a directory. They write the base case and recursive step in plain English before touching code. Groups share decompositions and debate edge cases.

Differentiate when an iterative solution is preferable to a recursive one, considering efficiency and readability.

Facilitation Tip

For the Recursion Decomposition Workshop, require students to write the base case and recursive step in separate colored markers to visually separate the two critical parts of their solution.

What to look for

Facilitate a class discussion using the prompt: 'Imagine you need to sort a large list of numbers. When might a recursive sorting algorithm like Merge Sort be a better choice than an iterative one like Bubble Sort, and when would the iterative approach be preferable?'

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 04

• Collaborative Problem-Solving
• 30 min · Individual

Individual Practice: Recursive Trace Diagrams

Students trace recursive calls for small inputs by drawing call trees on paper and annotating return values at each level. After comparing with a partner, they predict the output of a modified version and verify by running the code.

Explain how a complex problem can be defined by a smaller version of itself.

Facilitation Tip

Have students draw each call on a separate sticky note during the Recursive Trace Diagrams activity so they physically see how the call stack grows and shrinks.

What to look for

Present students with a simple recursive function (e.g., a flawed factorial function). Ask them to trace its execution for n=3 on paper, identifying where it deviates from the correct logic or where a stack overflow might occur. Collect these traces for review.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

A few notes on teaching this unit

Teachers should start by modeling the act of tracing a recursive function slowly, emphasizing the base case as the anchor and the return values as the bridge back up. Avoid rushing to the final answer; instead, linger on each step so students notice how pending calls wait for the next return. Research shows that students grasp recursion better when they first experience it through physical simulation before moving to abstract code, so prioritize kinesthetic activities early in the unit.

By the end of these activities, students should trace recursive solutions accurately, design correct base cases and recursive steps, and explain why recursion is a valid strategy for specific problems. They should also recognize when recursion is appropriate and when it is not.

---

Watch Out for These Misconceptions

• During Human Recursion Stack, watch for students who expect the final recursive call to produce the answer directly.

  After the activity, prompt students to say their return value out loud as they step back, reinforcing that the base case is the first concrete answer and return values propagate upward through each pending call.

• During the Recursion Decomposition Workshop, students may assume recursion always uses significantly more memory than loops.

  Have students measure the actual stack depth for moderate inputs and compare it to loop overhead, using small input sizes to demonstrate that recursion’s memory use is proportional to depth, not inherently prohibitive.

• During the Base Case Detective activity, students may believe every recursive function must have exactly one base case.

  Provide examples with multiple base cases (like Fibonacci) and ask pairs to identify all base cases before designing their recursive step, making the need for multiple base cases explicit.

---

Methods used in this brief

• Simulation Game
• Think-Pair-Share
• Collaborative Problem-Solving