Materials & Prep
- Projector or board.
- One-page handout or shared document with the three Java tasks in this lesson and a four-row call-stack table: call, value held, waits for, return value.
- Students need a Java IDE or compiler for the independent method. Pair students if devices are limited.
Display
public static int sumDigits(int n) { if (n == 0) return 0; return n % 10 + sumDigits(n / 10); }
Ask“When sumDigits(305) finally reaches n == 0, why is the answer not 0?” Students commit individually to 0, 8, or “error,” then draw the sequence of calls they think occurs. Ask them to recall what a loop version would do: repeatedly remove the last digit and keep a running total. Do not resolve predictions yet.
Turn and talkPartners compare whether sumDigits(305) completes the call with 305 before moving to 30, or whether something is left unfinished. Listen for the misconception that the recursive call replaces or erases the earlier call.
Direct instruction
7–20 minExplainA recursive method has two required parts. The base case stops recursion and returns a direct answer. The recursive call solves a smaller version of the same problem and must move toward the base case.
AnalogyTreat the call stack like a stack of lunch trays. Each call gets its own tray holding its own n and a note about what it still must do. A tray cannot be finished until the tray placed on top of it is removed.
Think aloudTrace sumDigits(305) in the call-stack table. “For n = 305, 305 % 10 is 5. I cannot return yet because I need sumDigits(30), so this frame waits with 5.” Record:
- sumDigits(305): holds 5, waits for sumDigits(30)
- sumDigits(30): holds 0, waits for sumDigits(3)
- sumDigits(3): holds 3, waits for sumDigits(0)
- sumDigits(0): base case, returns 0
Continue upward: sumDigits(3) returns 3 + 0 = 3; sumDigits(30) returns 0 + 3 = 3; sumDigits(305) returns 5 + 3 = 8. Emphasize that calls move downward, but return values move upward.
MisconceptionRun the tempting but incorrect base case, if (n == 1) return 1;. Ask what happens for sumDigits(0). It does not stop and n / 10 remains 0 forever. A base case must cover the smallest valid input, not merely a value that seems convenient.
Check for understandingStudents hold up or enter the return values, in order, for sumDigits(42): the base case returns 0, then the frames return 4, then 6. Ask one student to name the exact recursive call and another to explain why it gets closer to the base case.
Display
public static String repeat(String word, int n) { if (n == 0) return ""; return word + repeat(word, n - 1); }
Have studentsIn pairs, fill the call-stack table for repeat("go", 3). Require both the calls and returns. Pause after the downward calls, then ask what each frame is waiting to add.
Expectedrepeat("go", 0) returns ""; then the returns are "go", "gogo", and "gogogo". Clarify that string concatenation happens as frames return, not before the next call begins.
Worked exampleCo-construct a method that returns the sum from n down to 1.
public static int sumTo(int n) { if (n == 0) return 0; return n + sumTo(n - 1); } For sumTo(3), record 3 waiting for sumTo(2), 2 waiting for sumTo(1), 1 waiting for sumTo(0), then returns 0, 1, 3, 6.
ScaffoldGive students this planning frame before they write: “Smallest valid input is . It returns . For a larger input, I use and call the method with .” Students may use the frame and the stack table throughout the lesson.
Independent work
34–50 minChallengeBuild and run this Java artifact. The method receives a nonnegative integer and returns the sum of its digits.
public static int sumDigits(int n) { // write this method }
Post these required tests
- sumDigits(0) returns 0
- sumDigits(7) returns 7
- sumDigits(305) returns 8
- sumDigits(1000) returns 1
Students first annotate their base case and recursive call in comments, then implement, run, and debug systematically. Require a brief note below the code: “My recursive input changes from to , so it reaches the base case because .”
CirculateAsk students to point to the currently active frame and say what it is waiting for. When code fails, have them test n = 0 before changing anything else. Watch for random edits and for n - 1, which would add every number rather than remove one digit.
SupportProvide the method skeleton with two blanks for students who need an entry point:
if () return ; return + sumDigits(); Have them use the 305 stack table to choose each expression.
ExtensionWrite countDigit(int n, int target), which returns how many times target appears in nonnegative n. Test countDigit(1001, 0) and explain why 0 itself needs a deliberate design decision.
Closing
50–55 minExit ticketWrite countDownTotal, label its base case and recursive call, and list the return values for countDownTotal(2).
public static int countDownTotal(int n) { // n is nonnegative; return n + (n - 1) + ... + 1 }
Expectedif (n == 0) return 0; return n + countDownTotal(n - 1);. The returns for n = 2 are 0, 1, 3. Collect or scan responses to identify whether students can both construct the method and trace its unwinding.