Recursive Problem Solving: Basics

Active learning works because recursion demands mental visualization of processes that unfold step by step, which static examples cannot capture. When students physically trace recursion trees or debug missing base cases in real code, they build durable mental models of how recursion unfolds, moving beyond abstract definitions into concrete understanding.

• Grade 12
• Computer Science
• 4 activities
• 20 min–35 min

Learning Objectives

1. Construct a recursive function to calculate the factorial of a non-negative integer.
2. Compare the execution flow and memory usage of recursive versus iterative solutions for a given problem.
3. Explain the critical role of the base case in terminating recursive function calls.
4. Analyze a simple problem and identify whether a recursive or iterative approach is more appropriate.
5. Trace the call stack for a basic recursive function, such as factorial calculation.

Problem-Based Learning

⏱ 30 min·Pairs

Pair Coding: Factorial Recursion

Pairs write a recursive factorial function in Python, including a base case for n=0 or 1. They test with inputs from 1 to 10, printing each recursive call. Discuss outputs and modify to return values only.

Prepare & details

How do you determine if a problem is better solved through recursion or iteration?

Facilitation Tip: During Pair Coding: Factorial Recursion, circulate and ask pairs to explain their recursive step aloud before coding it to surface misconceptions early.

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

Problem-Based Learning

⏱ 25 min·Small Groups

Small Groups: Recursion Tree Drawing

Groups draw recursion trees for Fibonacci(5), labeling sub-calls and base cases. Compare trees for factorial(4). Share drawings class-wide to identify patterns in call depth.

Prepare & details

Explain the role of the base case in preventing infinite execution in recursive functions.

Facilitation Tip: For Recursion Tree Drawing, provide graph paper or digital tools and limit each group to a single function to prevent overcomplicating their first attempt.

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

Problem-Based Learning

⏱ 35 min·Whole Class

Whole Class: Tower of Hanoi Demo

Project a recursive Tower of Hanoi solution for 3 disks. Class predicts moves step-by-step, then runs code. Vote on base case modifications and observe effects.

Prepare & details

Construct a recursive solution for a simple problem like factorial calculation.

Facilitation Tip: In the Tower of Hanoi Demo, pause after each move to ask students to predict the next recursive call before it happens, reinforcing pattern recognition.

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

Problem-Based Learning

⏱ 20 min·Individual

Individual: Iteration vs Recursion Trace

Students trace recursive and iterative Fibonacci(6) on paper, counting operations and stack frames. Code both versions and time execution for n=30.

Prepare & details

How do you determine if a problem is better solved through recursion or iteration?

Facilitation Tip: For the Iteration vs Recursion Trace, require students to label each stack frame with variable values to make overhead concrete and memorable.

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 concrete examples students already know, like factorial, before moving to abstract problems. Avoid diving too quickly into mathematical proofs of recursion’s correctness, as students benefit more from tracing and debugging first. Research suggests pairing recursion with visual tools like recursion trees improves comprehension more than lectures alone. Emphasize that recursion is a design tool, not just a performance choice, and highlight readability wins in problems that naturally fit divide and conquer.

What to Expect

Successful learning looks like students confidently identifying base cases and recursive steps in new problems, tracing execution paths without confusion, and articulating trade-offs between recursion and iteration. They should also recognize when recursion adds clarity despite its overhead and avoid common pitfalls like infinite recursion or stack overflows.

Watch Out for These Misconceptions

Common Misconception

During Pair Coding: Factorial Recursion, watch for students assuming recursion is faster because it looks elegant.

What to Teach Instead

Guide pairs to insert print statements tracing each call and return, then count operations versus an iterative loop to reveal recursion’s overhead in time and memory.

Common Misconception

During Small Groups: Recursion Tree Drawing, watch for students omitting base cases or recursive steps entirely.

What to Teach Instead

Ask groups to label each node in their tree with the base case or recursive step it represents, forcing them to confront missing elements directly.

Common Misconception

During Individual: Iteration vs Recursion Trace, watch for students treating base cases as optional even in simple problems.

What to Teach Instead

Have students intentionally remove the base case in their trace and run the code, then analyze the resulting stack overflow or infinite loop together.

Assessment Ideas

Quick Check

After Pair Coding: Factorial Recursion, present a pseudocode snippet of a recursive function (e.g., factorial) and ask students to identify the base case and recursive step. Collect responses to identify gaps in identifying structural components.

Exit Ticket

After Individual: Iteration vs Recursion Trace, provide the problem of calculating the sum of numbers from 1 to n. Ask students to write a recursive function and explain why their base case is correct, assessing their ability to design proper recursion.

Discussion Prompt

During Whole Class: Tower of Hanoi Demo, initiate a discussion comparing a recursive solution for finding the nth Fibonacci number with an iterative one. Ask students to articulate trade-offs in readability and performance, revealing their understanding of recursion’s strengths and weaknesses.

Extensions & Scaffolding

• Challenge students to write a recursive function that prints a binary tree in-order traversal, then compare its readability to an iterative version.
• For students struggling with base cases, provide partially completed recursive functions with missing bases and ask them to fill in and test.
• Deeper exploration: Have students research tail recursion and convert their factorial function to use it, then measure and compare stack usage.

Key Vocabulary

Recursion	A programming technique where a function calls itself to solve a problem by breaking it down into smaller, identical sub-problems.
Base Case	The condition within a recursive function that stops the recursion, preventing infinite loops and providing a direct answer for the smallest sub-problem.
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 program to keep track of active function calls, including their local variables and return addresses; each recursive call adds a new frame to the stack.