Computer Science · Grade 12 · Algorithm Analysis and Optimization · Term 2

Recursive Problem Solving: Basics

Mastering the divide and conquer approach to solve complex problems by breaking them into smaller sub-problems.

• Ontario Curriculum Expectations
• CS.P.15
• CS.AA.5

About This Topic

Recursive problem solving introduces students to the divide and conquer strategy, where complex problems break into identical smaller sub-problems. In Grade 12 Computer Science, students learn to identify suitable recursive problems, such as factorial calculation or Fibonacci sequences, and construct functions with a base case to halt recursion and prevent infinite loops. They compare recursion to iteration, analyzing when recursion simplifies code despite added overhead from function calls and stack usage. This aligns with Ontario standards CS.P.15 and CS.AA.5, emphasizing algorithm design and optimization.

Within the Algorithm Analysis and Optimization unit, recursion builds skills in problem decomposition and trace execution, preparing students for advanced topics like dynamic programming. Students explore recursion trees to visualize call stacks, revealing depth limits and space complexity. These concepts foster computational thinking, as students recognize patterns in problems like tree traversals or searching sorted lists.

Active learning shines here because recursion feels abstract until students code, run, and debug their own functions. Pair programming recursive solutions or tracing calls on whiteboards turns mental models into visible processes, helping students spot base case errors and grasp stack growth intuitively.

Key Questions

1. How do you determine if a problem is better solved through recursion or iteration?
2. Explain the role of the base case in preventing infinite execution in recursive functions.
3. Construct a recursive solution for a simple problem like factorial calculation.

Learning Objectives

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

Before You Start

Introduction to Functions

Why: Students need to understand how functions work, including parameters, return values, and scope, before they can grasp how functions call themselves.

Basic Control Flow (Loops)

Why: Understanding iterative solutions provides a point of comparison for appreciating the structure and logic of recursion.

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.

Watch Out for These Misconceptions

Common Misconception

Recursion is always faster than iteration.

What to Teach Instead

Recursion often uses more time and space due to repeated function calls and stack overhead. Students discover this through active tracing of recursion trees in pairs, comparing operation counts to iterative loops and measuring runtimes.

Common Misconception

Any problem solvable iteratively works recursively without changes.

What to Teach Instead

Recursive versions need base cases and proper sub-problem returns, unlike loops. Group debugging sessions reveal stack overflow errors from missing bases, building careful design habits.

Common Misconception

Base cases are optional if the problem is simple.

What to Teach Instead

Without base cases, recursion loops infinitely. Hands-on coding challenges where students intentionally omit bases and observe crashes clarify the necessity, reinforcing trace practice.

Active Learning Ideas

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.

30 min·Pairs

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.

25 min·Small Groups

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.

35 min·Whole Class

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.

20 min·Individual

Real-World Connections

• Computer scientists use recursion to implement algorithms for parsing hierarchical data structures like XML or JSON files, essential for web development and data exchange.
• In operating systems, recursion is employed for tasks like traversing directory trees to manage files and folders, allowing efficient navigation of complex file systems.
• Game developers utilize recursion for pathfinding algorithms in video games, enabling characters to navigate complex game environments by breaking down the path into smaller segments.

Assessment Ideas

Quick Check

Present students with a pseudocode snippet of 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 removed.

Exit Ticket

Provide students with the problem of calculating the sum of numbers from 1 to n. Ask them to write a recursive function for this problem and briefly explain why their chosen base case is correct.

Discussion Prompt

Facilitate a class discussion comparing a recursive solution for finding the nth Fibonacci number with an iterative one. Ask students to articulate the trade-offs in terms of code readability and potential performance differences.

Frequently Asked Questions

How do you teach students to identify recursive problems?

Start with key questions like suitability for divide and conquer. Use examples such as factorial or binary search, contrasting with linear scans. Have students classify problems in small groups, justifying choices based on sub-problem similarity. This builds pattern recognition over rote memorization.

What role does the base case play in recursion?

The base case stops recursion by handling the simplest input directly, preventing infinite calls. Students construct functions like factorial where if n <= 1, return 1. Tracing calls visually shows how it unwinds the stack, essential for understanding execution flow.

How can active learning help students understand recursion?

Active approaches like pair coding recursive functions and drawing recursion trees make stack calls visible and debuggable. Students experience base case failures firsthand through crashes, then fix them collaboratively. Whole-class demos of puzzles like Tower of Hanoi reveal divide-and-conquer in action, turning abstract theory into concrete skills.

When to choose recursion over iteration in algorithms?

Opt for recursion when problems naturally decompose into self-similar sub-problems, like tree traversals, and code clarity matters more than efficiency. Analyze time/space via traces; iteration suits tail-recursive cases optimizable by compilers. Students practice by refactoring code versions and benchmarking.