Implementing Recursive Algorithms

Active learning works well here because recursive thinking is abstract, and students need to see the call stack in action to grasp how each recursive call builds on the last. Working in pairs or small groups turns the invisible process of recursion into a shared visual and tactile experience, reducing confusion about base cases and stack frames.

• Grade 11
• Computer Science
• 4 activities
• 25 min–45 min

Learning Objectives

1. Design a recursive function to calculate the factorial of a non-negative integer, identifying the base case and recursive step.
2. Implement a recursive function to generate terms of the Fibonacci sequence, explaining the role of base cases.
3. Compare the code conciseness and readability of recursive versus iterative solutions for calculating factorials.
4. Analyze the potential for stack overflow errors when implementing deeply recursive functions for problems like Fibonacci.
5. Demonstrate a recursive tree traversal (e.g., inorder) by writing code and tracing its execution.

Collaborative Problem-Solving

⏱ 35 min·Pairs

Pair Programming: Factorial and Fibonacci Coders

Pairs write recursive functions for factorial and Fibonacci, test with inputs from 0 to 10, and trace calls on paper. They then rewrite one iteratively and compare outputs and code length. Discuss which approach suits each problem.

Prepare & details

Design a recursive function to solve a given problem, identifying the base case and recursive step.

Facilitation Tip: Before starting Pair Programming, ask each pair to sketch the call stack on paper for the first three steps of their chosen function to ensure they see how the frame grows and shrinks.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

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

Collaborative Problem-Solving

⏱ 45 min·Small Groups

Small Groups: Tree Traversal Simulator

Groups draw binary trees on paper and implement inorder, preorder, postorder traversals recursively. They simulate execution by marking visit order with colors and swap trees to test peers' code. Note differences in output sequences.

Prepare & details

Compare the readability and conciseness of recursive versus iterative solutions for specific problems.

Facilitation Tip: For the Tree Traversal Simulator, have groups use index cards labeled with node values and arrows to physically rearrange the tree and trace the path together.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

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

Collaborative Problem-Solving

⏱ 25 min·Whole Class

Whole Class: Stack Overflow Hunt

Project recursive code with deep calls; class predicts outcomes step-by-step on shared screen. Run in IDE to trigger overflow, then brainstorm limits like tail recursion. Vote on fixes via polls.

Prepare & details

Evaluate the potential for stack overflow errors in deeply recursive functions.

Facilitation Tip: During the Stack Overflow Hunt, bring in a stack of paper cups to model the call stack, letting students watch the stack grow and topple when limits are reached.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

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

Collaborative Problem-Solving

⏱ 30 min·Individual

Individual: Efficiency Duel

Students code recursive and iterative Fibonacci, time runs for n=35 using timers, and graph results. Submit reports comparing space use and readability with code snippets.

Prepare & details

Design a recursive function to solve a given problem, identifying the base case and recursive step.

Facilitation Tip: In the Efficiency Duel, provide a timer app so students can measure milliseconds and compare recursive versus iterative results directly on their devices.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

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

Teaching This Topic

Experienced teachers approach recursion by first making the invisible visible: use whiteboard sketches, physical props, or digital animations to show how each call adds a frame. Avoid starting with the most complex example; begin with factorial because it has one clear base case and one recursive step. Emphasize tracing over writing early on, because students often confuse the structure of a recursive function with its implementation. Research shows that students benefit from comparing recursive and iterative solutions side by side to understand trade-offs in clarity and performance.

What to Expect

Successful learning looks like students confidently identifying base cases and recursive steps in multiple problems, tracing recursive calls on paper or whiteboards without prompting, and justifying why a recursive approach fits one problem but not another. You’ll see students debug missing base cases independently and propose optimizations like memoization after timing challenges.

Watch Out for These Misconceptions

Common Misconception

During Pair Programming: Factorial and Fibonacci Coders, watch for students assuming recursive solutions are always faster.

What to Teach Instead

During Pair Programming, ask each pair to time both their recursive and iterative solutions using their devices’ timers, then compare results and discuss why naive recursion is slower for Fibonacci due to repeated calculations.

Common Misconception

During Pair Programming: Factorial and Fibonacci Coders, watch for students treating base cases as optional.

What to Teach Instead

During Pair Programming, have each pair trace their function on paper with sample inputs, stopping at each call to confirm the base case is reached and the stack unwinds correctly.

Common Misconception

During Whole Class: Stack Overflow Hunt, watch for students believing stack overflow only happens with extremely large inputs.

What to Teach Instead

During Whole Class, use the stack of paper cups to simulate a call stack and gradually increase the depth until the cups topple, showing how moderate depths can cause overflow if base cases are missing or inputs are large.

Common Misconception

Assessment Ideas

Quick Check

Present students with a pseudocode snippet for a recursive function (e.g., factorial). Ask them to identify the base case and the recursive step, and explain what would happen if the base case were missing.

Discussion Prompt

Pose the question: 'When might you choose a recursive solution over an iterative one, even if the iterative solution is more memory efficient? Discuss specific scenarios and the trade-offs involved, considering factors like code clarity and problem structure.'

Exit Ticket

Give students a simple problem (e.g., sum of numbers from 1 to n). Ask them to write a recursive function to solve it and then write one sentence explaining a potential drawback of their solution.

Extensions & Scaffolding

• Challenge: Ask students to implement memoization in their Fibonacci solution and measure the speed difference using the Efficiency Duel setup.
• Scaffolding: Provide a partially completed recursive function for tree traversal with blanks for the recursive calls and base case, guiding students to fill in the logic step by step.
• Deeper exploration: Introduce tail recursion with an example where the recursive call is the last operation, and discuss how this can be optimized by some compilers to avoid stack growth.

Key Vocabulary

Recursion	A programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems.
Base Case	The condition within a recursive function that stops the recursion, preventing infinite calls and providing a direct answer for the simplest input.
Recursive Step	The part of a recursive function where it calls itself with a modified input, moving closer to the base case.
Call Stack	A data structure used by a computer to keep track of active function calls; in recursion, each function call adds a 'frame' to the stack.
Stack Overflow Error	An error that occurs when a program runs out of memory allocated for the call stack, often caused by excessively deep or infinite recursion.