Recursive Algorithms

Recursion challenges students to hold multiple function calls in their minds at once, a skill that improves their debugging and design thinking. Active learning makes this abstract idea concrete through physical movement, peer discussion, and hands-on tracing that reduces cognitive load.

• 10th Grade
• Computer Science
• 4 activities
• 20 min–35 min

Learning Objectives

1. Explain the role of the base case and recursive step in terminating a recursive function.
2. Compare the computational efficiency and memory usage of iterative and recursive solutions for factorial calculation.
3. Analyze the potential for stack overflow errors when implementing recursive algorithms with deep call stacks.
4. Design a simple recursive function to solve a problem, such as calculating the sum of a list of numbers.
5. Trace the execution of a recursive function, identifying the state of variables at each function call.

Role Play

⏱ 25 min·Whole Class

Role Play: Human Call Stack

Assign one student per recursive call for a small example like factorial of 4. Each student is one stack frame: they receive a value, write it down, call the next student forward, wait for a return value, compute their result, and report back. The class watches the call stack build and unwind physically, making the base case and unwinding behavior concrete.

Prepare & details

Explain the base case and recursive step in a recursive function.

Facilitation Tip: During the Human Call Stack, have students physically stand up as they call the function and sit down only when they hit the base case so the unwinding is visible to the whole room.

Setup: Open space or rearranged desks for scenario staging

Materials: Character cards with backstory and goals, Scenario briefing sheet

• Apply
• Analyze
• Evaluate
• Social Awareness
• Self-Awareness

Think-Pair-Share

⏱ 20 min·Pairs

Think-Pair-Share: Iterative vs. Recursive

Present two implementations of the same function (summing 1 to n): one iterative, one recursive. Students individually analyze which they find clearer and what trade-offs each approach has. Pairs discuss, then share one advantage and one disadvantage of each. Sets up the stack overflow discussion and builds the analytical habit of comparing implementation strategies.

Prepare & details

Compare iterative and recursive solutions for problems like factorial calculation.

Facilitation Tip: For the Think-Pair-Share, give pairs one iterative and one recursive solution to the same problem so they must compare mechanics, not just abstract ideas.

Setup: Standard classroom seating; students turn to a neighbor

Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs

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

Inquiry Circle

⏱ 35 min·Small Groups

Inquiry Circle: Trace the Stack

Groups of 3 receive a recursive function and a specific input. Each group member traces one level of the call stack, writing what value is passed in, what the recursive call returns, and what the final return value is. Groups assemble the full trace and verify it matches running the function, building confidence in reading recursive code.

Prepare & details

Analyze the potential for stack overflow errors in recursive algorithms.

Facilitation Tip: While students Trace the Stack, circulate with sticky notes and label each frame with the input and the return value to make the process visible.

Setup: Groups at tables with access to source materials

Materials: Source material collection, Inquiry cycle worksheet, Question generation protocol, Findings presentation template

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Problem-Based Learning

⏱ 30 min·Small Groups

Debugging Challenge: Missing Base Case

Provide two recursive functions: one correct, one missing a base case. Students run both (or trace by hand) and observe the behavioral difference. Groups document what happens to the call stack in each case and rewrite the broken function with a correct base case, connecting the concept directly to a real implementation failure.

Prepare & details

Explain the base case and recursive step in a recursive function.

Facilitation Tip: Hand out colored markers during the Missing Base Case challenge so students can highlight the missing clause before rewriting the function.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

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

Teaching This Topic

Start with the physical role-play to anchor the concept in body memory before moving to code. Use pair comparisons between iterative and recursive solutions to highlight mechanical differences, not just similarities. Avoid comparing recursion only to loops; instead, focus on state management through the call stack so students see recursion as a distinct paradigm.

What to Expect

Students will describe how the call stack grows and shrinks, explain the role of the base case, and decide when to use recursion over iteration. By the end, they should be able to write a simple recursive function and justify its design choices.

Watch Out for These Misconceptions

Common Misconception

During the Human Call Stack activity, watch for students who say recursive functions always run forever because they keep calling themselves.

What to Teach Instead

Use the physical demonstration to show how each student sits down when they reach the base case, proving the stack unwinds and the function terminates reliably.

Common Misconception

During the Think-Pair-Share activity, watch for students who claim recursion is just a loop written differently and that the two are always equivalent.

What to Teach Instead

Point to the two different implementations they compared and ask them to trace one step of each; highlight how the call stack stores state in recursion but variables do in iteration.

Assessment Ideas

Quick Check

After the Collaborative Investigation, present a pseudocode snippet and ask students to identify the base case and the recursive step, and write one sentence explaining how the input changes in the recursive step.

Discussion Prompt

During the Think-Pair-Share, pose the question: 'When might a recursive solution be preferred over an iterative one, and vice versa?' Guide students to discuss trade-offs like code readability, potential for stack overflow, and performance.

Exit Ticket

After the Debugging Challenge, give students a simple problem like calculating powers (e.g., 2^n) and ask them to write a recursive function with a base case and recursive step, then state the expected output for 2^3.

Extensions & Scaffolding

• Challenge: Ask students to write a recursive solution for tree traversal and describe how the call stack mirrors the tree structure.
• Scaffolding: Provide a partially completed trace table with some frames filled in so students only need to compute return values.
• Deeper exploration: Have students research tail recursion and compare stack usage between recursive and iterative versions of the same function.

Key Vocabulary

Recursion	A programming technique where a function calls itself to solve a problem. It breaks down a problem into smaller, self-similar subproblems.
Base Case	The condition within a recursive function that stops the recursion. It represents the simplest form of the problem that can be solved directly.
Recursive Step	The part of a recursive function where the function calls itself with modified input, moving closer to the base case.
Call Stack	A data structure used by a computer to keep track of active function calls. Each function call adds a frame to the stack, and returns remove frames.
Stack Overflow Error	An error that occurs when a program runs out of space on the call stack, typically due to infinite recursion or excessively deep recursion.