Introduction to Recursion

Recursion is abstract, so active learning helps students visualize how each call works. Pair tracing, modeling, and debugging make the stack of calls concrete rather than abstract. When students manipulate examples by hand, they internalize why the base case matters and how memory grows with each call.

• Grade 10
• Computer Science
• 4 activities
• 15 min–30 min

Learning Objectives

1. Compare and contrast the execution flow of iterative and recursive solutions for a given problem, such as calculating factorials.
2. Analyze the base case and recursive step of a provided recursive function to determine its correctness.
3. Predict the output of a simple recursive function by tracing its execution path, including identifying potential infinite recursion scenarios.
4. Design a basic recursive function to solve a problem that can be broken down into self-similar subproblems.

Flipped Classroom

⏱ 20 min·Pairs

Pair Tracing: Factorial Calls

Pairs receive printed recursive factorial code and trace calls step-by-step on worksheets, noting base cases and stack growth. They compute results manually, then compare to iterative loops. Pairs share one insight with the class.

Prepare & details

Differentiate between iterative and recursive approaches to problem-solving.

Facilitation Tip: During Pair Tracing: Factorial Calls, have students write each call on a separate sticky note to build a visible call stack on the desk.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Flipped Classroom

⏱ 30 min·Small Groups

Small Groups: Tower of Hanoi Model

Groups use stacked blocks or cups to simulate Tower of Hanoi moves, identifying the base case for one disk and recursive steps for larger towers. They record moves in pseudocode. Groups present their solutions.

Prepare & details

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

Facilitation Tip: During Small Groups: Tower of Hanoi Model, assign roles so one student moves disks while another records the recursive steps aloud.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Flipped Classroom

⏱ 25 min·Whole Class

Whole Class: Infinite Loop Hunt

Project buggy recursive code missing a base case. Students use digital polls to vote on fixes, then discuss as a class while you step through execution. Revise code live based on input.

Prepare & details

Predict potential issues like infinite recursion and stack overflow.

Facilitation Tip: During Whole Class: Infinite Loop Hunt, run sample code live and pause execution to ask students to predict the next call before revealing it.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Flipped Classroom

⏱ 15 min·Individual

Individual: Fibonacci Sketch

Students sketch recursive Fibonacci call trees on paper, marking redundant calls and stack depth. They predict output for small inputs and note overflow risks. Submit for quick peer review.

Prepare & details

Differentiate between iterative and recursive approaches to problem-solving.

Facilitation Tip: During Individual: Fibonacci Sketch, provide graph paper so students draw the call tree with branches for each recursive step.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Teaching This Topic

Start with the stack analogy: each call is a plate added to a tower. Teach students to read recursive functions from the bottom up, locating the base case first. Avoid rushing into memoization; let students experience the inefficiency of naive recursion firsthand. Research shows that tracing beats lecturing for deep understanding of recursion, so allocate time for deliberate practice with pens, sticky notes, and colored pencils.

What to Expect

Students can trace recursive calls step by step, identify base cases and recursive steps clearly, and explain when recursion becomes inefficient. They justify their reasoning using execution traces and compare recursive and iterative approaches with confidence.

Watch Out for These Misconceptions

Common Misconception

During Pair Tracing: Factorial Calls, watch for students assuming recursion is always faster.

What to Teach Instead

Have pairs time their manual execution versus a simple loop, then discuss why repeated subproblem calls in naive recursion slow things down and how memoization changes that.

Common Misconception

During Small Groups: Tower of Hanoi Model, watch for students thinking the base case is optional.

What to Teach Instead

Ask groups to remove the base case from their written rules and simulate the infinite stack of moves, then insert a base case to restore a finite sequence.

Common Misconception

During Individual: Fibonacci Sketch, watch for students believing recursive calls use no extra memory.

What to Teach Instead

Require students to draw each call as a stack frame on their graph paper, then count frames for Fibonacci(5) to visualize growth and overflow risk.

Assessment Ideas

Quick Check

After Pair Tracing: Factorial Calls, show a broken recursive factorial with a missing base case. Ask students to circle the missing return statement and explain why the function would never stop.

Exit Ticket

After Individual: Fibonacci Sketch, give code for recursive factorial and ask students to write factorial(3) output and list the sequence of calls and returns as a stack diagram.

Discussion Prompt

During Whole Class: Infinite Loop Hunt, pose the question, 'When might recursion be preferred even if it uses more memory?' and have students cite hierarchical data or mathematical definitions from the examples they’ve traced.

Extensions & Scaffolding

• Challenge: Ask students to rewrite their naive Fibonacci function using memoization and compare run times.
• Scaffolding: Provide partially filled call trees for factorial(4) so students label each step.
• Deeper exploration: Introduce mutual recursion with a simple odd-even checker, then challenge students to trace the alternating calls.

Key Vocabulary

Recursion	A problem-solving technique where a function calls itself to solve smaller instances of the same problem until a stopping condition is met.
Base Case	The condition within a recursive function that stops the recursion, preventing an infinite loop. 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 that keeps track of active function calls. In recursion, each function call adds a new frame to the stack, and each return removes one.
Stack Overflow	An error that occurs when a program runs out of memory in the call stack, often caused by excessively deep or infinite recursion.