Computer Science · 12th Grade

Active learning ideas

Advanced Recursion: Backtracking and Memoization

Active learning works for advanced recursion because students need to see recursion’s power and pitfalls in real time. When they trace paths, cache results, or simulate pruning, they move from abstract ideas to concrete understanding. These activities force them to confront inefficiency, repetition, and constraint satisfaction in ways that lectures cannot.

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

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

Activity 01

• Problem-Based Learning
• 35 min · Pairs

Problem Solving: Maze Backtracking Challenge

Print 4x4 grid mazes on paper. Student pairs trace all possible paths from start to exit using a systematic backtracking strategy: mark a cell, move forward, backtrack when stuck, never revisit. After solving manually, groups compare their path-finding process and abstract it into pseudocode.

Design a recursive solution that incorporates backtracking to explore all possible paths.

Facilitation Tip

During the Maze Backtracking Challenge, give students a dry-erase grid to encourage trial, error, and immediate revision without fear of erasing mistakes.

What to look for

Present students with a small, incomplete maze. Ask them to trace a backtracking path on paper, clearly marking dead ends and the final solution. Then, ask them to identify one point where a naive recursive approach would re-explore a path.

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

Activity 02

• Think-Pair-Share
• 20 min · Pairs

Think-Pair-Share: Fibonacci Call Tree Analysis

Show students a partial call tree for fib(6) computed without memoization. Students count redundant calls individually, then discuss with a partner how memoization would eliminate them. Pairs share their annotated diagrams with the class to generalize the benefit.

Justify the use of memoization to improve the efficiency of certain recursive algorithms.

Facilitation Tip

In the Fibonacci Call Tree Analysis, have students physically draw the call tree on chart paper, labeling repeated subtrees to make overlapping subproblems visible.

What to look for

Pose the following: 'Consider the problem of calculating the nth Fibonacci number. Explain why a naive recursive solution is inefficient and how memoization addresses this inefficiency. What data structure would you use to store the computed Fibonacci numbers and why?'

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

Activity 03

• Gallery Walk
• 30 min · Small Groups

Gallery Walk: Memoization Before and After

Post pairs of code snippets and call trees around the room: one without memoization and one with. Students annotate each pair with the time complexity and number of unique subproblems computed. A class discussion follows to generalize when memoization is most impactful.

Compare the performance benefits of dynamic programming approaches over naive recursion.

Facilitation Tip

For the Gallery Walk, require each pair to post their before-and-after code side by side so observers can see the exact change memoization makes in execution time.

What to look for

Students work in pairs to implement a recursive function for a simple combinatorial problem (e.g., generating subsets). One student implements a naive recursive version, and the other implements a memoized version. They then swap code and use provided test cases to compare execution times and identify potential bugs in each other's implementation.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

Activity 04

• Simulation Game
• 40 min · Whole Class

Simulation Game: N-Queens Backtracking Theater

Use a large grid taped on the floor and student volunteers as queens. The class guides volunteers through placing queens row by row, calling out conflicts and directing backtracks. After the physical run, students code the solution and compare runtime with a brute-force approach.

Design a recursive solution that incorporates backtracking to explore all possible paths.

Facilitation Tip

In the N-Queens Backtracking Theater, rotate roles every two minutes so students experience both the recursive solver and the constraint-checker perspectives.

What to look for

Present students with a small, incomplete maze. Ask them to trace a backtracking path on paper, clearly marking dead ends and the final solution. Then, ask them to identify one point where a naive recursive approach would re-explore a path.

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

A few notes on teaching this unit

Start with a tiny problem students can solve by hand, then break it by adding scale. Teach recursion as a search strategy first, then layer optimization through memoization. Avoid teaching memoization as a magic fix; instead, show how it transforms exponential time into polynomial time. Research shows students grasp recursion better when they compare naive and optimized versions of the same problem side by side.

Students will demonstrate that they can trace recursive calls, explain when and why to add memoization or backtracking, and justify choices between naive and optimized solutions. They should articulate the trade-offs between completeness and efficiency in search problems.

---

Watch Out for These Misconceptions

• During the Gallery Walk, watch for students who claim memoization and dynamic programming are interchangeable after seeing a memoized recursive solution.

  Ask them to trace the execution of a bottom-up dynamic programming table for Fibonacci and compare it to their memoized recursive version. Highlight how the table fills iteratively versus how memoization caches on demand.

• During the N-Queens Backtracking Theater, watch for students who assume the first valid solution found is optimal.

  Have them run the simulation twice: once to find any solution and once to find all solutions. Then ask which version required more time and why finding all solutions matters for optimization.

• During the Fibonacci Call Tree Analysis, watch for students who think memoization helps every recursive problem.

  Give them a recursive problem without overlapping subproblems, like a binary tree traversal without repeated nodes. Ask them to try memoizing it and explain why the overhead doesn’t improve performance.

---

Methods used in this brief

• Problem-Based Learning
• Think-Pair-Share
• Gallery Walk
• Simulation Game