Recursion: Concepts and Base Cases

Recursion can feel abstract to students until they see the call stack grow and shrink. Active learning lets them trace the process step by step, turning invisible steps into visible patterns. Pairs and groups make the moment of recursion’s unwinding clearer than any lecture alone could do.

• Class 12
• Computer Science
• 4 activities
• 25 min–40 min

Learning Objectives

1. Explain the concept of a recursive function, including its self-referential nature and the need for a termination condition.
2. Identify and analyze the base case and recursive step in given recursive functions for problems like factorial and Fibonacci.
3. Compare and contrast the execution flow of iterative and recursive solutions for a given problem, such as calculating the nth Fibonacci number.
4. Calculate the output of simple recursive functions by manually tracing the call stack.
5. Design a basic recursive function to solve a simple problem, given a clear problem statement and constraints.

Problem-Based Learning

⏱ 30 min·Pairs

Pair Tracing: Factorial Calls

Pairs draw recursion trees for factorial(5) on paper, labelling base cases and return values step by step. They then trace Fibonacci(6), noting stack depth. Pairs discuss and compare their diagrams with the class.

Prepare & details

Explain the fundamental principles of recursion and its application in problem-solving.

Facilitation Tip: During Pair Tracing, ask each pair to write each function call on a separate sticky note so the growing stack becomes a physical tower on the desk.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Problem-Based Learning

⏱ 40 min·Small Groups

Small Group Debug: Base Case Fix

Provide small groups with buggy recursive code for sum of numbers lacking a base case. Groups identify the issue, add the base case, and test with print statements. Share fixes in a class gallery walk.

Prepare & details

Analyze the role of a base case in preventing infinite recursion.

Facilitation Tip: In Small Group Debug, give groups a print-out of the code with deliberate missing base cases; let them run it once to crash, then fix it together.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Problem-Based Learning

⏱ 25 min·Whole Class

Whole Class: Human Recursion Chain

Students line up to represent recursive calls for Fibonacci(4), passing values backward from base cases. The chain 'unwinds' to compute the result. Debrief on stack overflow risks with a too-long chain.

Prepare & details

Compare iterative and recursive solutions for common problems like Fibonacci sequences.

Facilitation Tip: For the Human Recursion Chain, use a stopwatch to time how long it takes the chain to unwind so students feel the cost of deep recursion.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Problem-Based Learning

⏱ 35 min·Individual

Individual Code: Simple Tower

Each student writes and runs a recursive function to print a tower of asterisks, varying height. They add print statements to observe call order, then modify for a base case change.

Prepare & details

Explain the fundamental principles of recursion and its application in problem-solving.

Facilitation Tip: When students build the Simple Tower individually, insist they draw the call tree first before coding to strengthen visual understanding.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Teaching This Topic

Teachers often start with the factorial example because it is familiar, but students also need to see the same pattern in tree traversals. Avoid rushing to code; spend time on tracing first. Research shows that students grasp recursion better when they physically act out the calls before writing them, so use human chains early. Emphasise the stack metaphor—show a glass of water filling and emptying as calls are made and returned—because concrete images anchor abstract ideas.

What to Expect

By the end of these activities, students should confidently identify the base case and recursive step in any simple function. They should be able to trace a recursive call and explain why a missing base case causes the programme to fail. Watch for students who can now compare recursion and iteration with reasoned arguments.

Watch Out for These Misconceptions

Common Misconception

During Pair Tracing, watch for students who think recursion always runs faster than iteration because no loop overhead exists.

What to Teach Instead

Use the sticky-note tower to show how each recursive call stores a return address, increasing memory usage. Ask pairs to count the number of notes for n=5 and compare it to the memory used by a loop that runs five times.

Common Misconception

During Small Group Debug, students may believe base cases are optional for small inputs.

What to Teach Instead

Give groups code that crashes for n=10 but seems to work for n=2. Have them run it and observe the stack overflow error, then insert the missing base case to fix it.

Common Misconception

During Human Recursion Chain, students might think recursion and iteration solve the same problems identically.

What to Teach Instead

Time the human chain for Fibonacci(4) and then simulate an iterative loop for the same value. Ask students to compare the number of steps and the clarity of each approach.

Assessment Ideas

Exit Ticket

After Pair Tracing, give students a simple recursive function to calculate the sum of numbers up to n. Ask them to write the base case and recursive step, then trace the execution for n=3, showing the output and the values stored on the call stack at each step.

Quick Check

During Small Group Debug, present two code snippets for factorial: one iterative and one recursive. Ask students to identify which is which and write one advantage of the iterative approach (space efficiency) and one advantage of the recursive approach (clarity for mathematical definitions).

Discussion Prompt

After the Human Recursion Chain, pose the question: 'What would happen if a recursive function did not have a base case?' Facilitate a class discussion where students explain the concept of infinite recursion and its consequences, such as a stack overflow error, using the chain timing data as evidence.

Extensions & Scaffolding

• Challenge: Ask early finishers to write a recursive function that calculates the nth triangular number and trace it for n=5 using the call-tree method.
• Scaffolding: Provide a partially completed call tree diagram for the Fibonacci sequence and ask students to fill in the missing branches before coding.
• Deeper exploration: Introduce tail recursion with an example like factorial and compare space usage with and without tail-call optimisation using a memory profiler tool.

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	A condition within a recursive function that stops the recursion, providing a direct answer for the smallest subproblem.
Recursive Step	The part of a recursive function where it calls itself with modified arguments, moving closer to the base case.
Call Stack	A mechanism used by programming languages to keep track of active function calls, including their local variables and return addresses. Each recursive call adds a new frame to the stack.