Introduction to Recursion

Active learning works for recursion because the concept demands students shift from linear thinking to understanding self-reference, a mental model that is hard to grasp without physical or visual representation. When students physically act out the call stack or trace code with peers, they build the spatial and temporal understanding needed to see how each recursive call connects to the next until the base case resolves.

• 11th Grade
• Computer Science
• 4 activities
• 25 min–35 min

Learning Objectives

1. Analyze the base case and recursive step in a provided recursive function.
2. Construct a simple recursive function to calculate the factorial of a non-negative integer.
3. Compare the execution trace of a recursive function with an equivalent iterative function.
4. Design a recursive solution for a problem that can be broken into self-similar subproblems.
5. Evaluate the efficiency of a recursive algorithm in terms of time complexity for simple cases.

Role Play

⏱ 30 min·Whole Class

Role Play: Human Call Stack

Students stand in a line, each representing one function call. The first student writes their argument on a sticky note and passes it to the next, who does the same, building the call stack. When the base case is reached, each student computes their return value from the one behind them and passes it back, simulating the recursive return.

Prepare & details

Explain the fundamental principles of recursive problem-solving.

Facilitation Tip: During the Human Call Stack activity, position students physically to mirror the stack frame order, so the first caller is at the bottom and the deepest call is at the top.

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

⏱ 25 min·Pairs

Think-Pair-Share: Find the Base Case

Provide pairs with three recursive function skeletons missing their base cases. Partners identify what is missing, add a base case, and predict what would happen without it. Pairs share their reasoning before the class tests each version.

Prepare & details

Analyze the base case and recursive step in a given recursive function.

Facilitation Tip: During the Think-Pair-Share Base Case activity, provide incomplete or intentionally broken examples so students must argue why a base case is missing or incorrect.

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

Concept Mapping

⏱ 35 min·Pairs

Paired Coding: Factorial and Fibonacci Trace

Partners implement recursive factorial and Fibonacci functions, then trace the execution of factorial(4) and fibonacci(5) step by step in writing before running the code. Comparing the written trace to actual debugger output helps students verify their mental model.

Prepare & details

Construct a simple recursive function to solve a problem like factorial or Fibonacci.

Facilitation Tip: During the Paired Coding Trace activity, require students to write both recursive and iterative versions side by side to highlight the structural differences in state management.

Setup: Tables with large paper, or wall space

Materials: Concept cards or sticky notes, Large paper, Markers, Example concept map

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Gallery Walk

⏱ 30 min·Small Groups

Gallery Walk: Recursion Pattern Analysis

Post four different recursive functions around the room (binary search, sum of list, string reversal, power function). Groups rotate and annotate each one by identifying the base case, recursive step, and what value gets returned at each level.

Prepare & details

Explain the fundamental principles of recursive problem-solving.

Facilitation Tip: During the Gallery Walk Pattern Analysis, post only student-generated examples so peers can critique naming conventions and structure rather than relying on provided templates.

Setup: Wall space or tables arranged around room perimeter

Materials: Large paper/poster boards, Markers, Sticky notes for feedback

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

Teaching This Topic

Experienced teachers approach recursion by first making the invisible visible. Use call-stack analogies early and often, since students struggle with the idea that each recursive call waits for the next one to finish. Avoid rushing into code; let students act out the process before writing functions. Research shows that students who manually trace examples with colored pens or sticky notes develop stronger conceptual models than those who only read code or watch animations.

What to Expect

By the end of these activities, students should be able to trace recursive calls, identify base cases correctly, and explain the difference between recursive and iterative approaches in their own words. Their work samples should show clear labeling of base cases and recursive steps, and their discussions should reflect confidence in predicting how recursion terminates.

Watch Out for These Misconceptions

Common Misconception

During the Human Call Stack activity, watch for students who describe recursion as 'just a loop written differently' when they equate the self-call with a repeated action in a loop.

What to Teach Instead

Use the physical positions to point out that each student in the stack is waiting for the next to finish, not repeating an action—this distinction makes the difference between iteration and recursion concrete.

Common Misconception

During the Think-Pair-Share Base Case activity, watch for students who assume any stopping condition is sufficient, even if it doesn’t cover all inputs.

What to Teach Instead

Ask students to test their base case with edge cases like n=0 or n=1 and explain why the base case must handle those inputs explicitly.

Common Misconception

During the Paired Coding Trace activity, watch for students who believe recursive solutions are always faster or more efficient than iterative ones.

What to Teach Instead

Have students profile their recursive and iterative versions with larger inputs to observe stack depth and overhead firsthand.

Assessment Ideas

Quick Check

After the Paired Coding Trace activity, present students with a recursive Fibonacci function and ask them to identify the base case and recursive step, then trace the execution for input 3 by writing the sequence of calls and return values on paper.

Exit Ticket

After the Think-Pair-Share Base Case activity, ask students to write a recursive function to sum numbers from 1 to n, label the base case, and explain why it works for all inputs.

Discussion Prompt

During the Gallery Walk Pattern Analysis activity, facilitate a class discussion where students compare their recursive factorial functions with iterative versions and explain the trade-offs in clarity, memory use, and speed for this problem.

Extensions & Scaffolding

• Challenge students to design a recursive function that prints a binary tree in in-order traversal, then compare it with an iterative version.
• For students who struggle, provide partially completed code with missing base cases or recursive steps and ask them to fill in the blanks with justification.
• Deeper exploration: Introduce tail recursion and have students rewrite a recursive factorial function to use tail recursion, then discuss why some languages optimize tail calls and others do not.

Key Vocabulary

Recursion	A programming technique where a function calls itself to solve a problem by breaking it down into smaller, identical subproblems.
Base Case	The condition within a recursive function that stops the recursion and provides a direct answer, preventing infinite loops.
Recursive Step	The part of a recursive function where it calls itself with modified input, moving closer to the base case.
Call Stack	A data structure that keeps track of active function calls, including their local variables and return addresses, crucial for understanding recursion execution.