CS210 · Block 4 · Lesson 33

Recursion vs Iteration: Weighing the Tradeoffs

Clarity vs cost · Stack growth · Stack overflow · When recursion wins · When to loop
At a glance: Lesson 32 left a question open: when is recursion actually the right choice? This lesson answers it. The same function can be written as a loop or as recursion and return the same answer, so the choice comes down to two axes: how clearly the code reads, and what it costs on the stack. You will see where a recursive forward walk runs out of stack and crashes, and where recursion is the cleaner, more practical option. The in-class widget runs both side by side; the lab has you convert the forward walks to iteration and keep the one case where recursion wins.
Contents
  1. Lesson Objectives
  2. Assigned Readings
  3. Pre-Class Work
  4. Lesson Materials and Overview
  5. In-Class Work
  6. After Class
1. Lesson Objectives

By the end of this lesson, cadets will be able to:

  1. Compare iterative and recursive solutions to the same problem. (Outcomes 1, 3)
  2. Evaluate tradeoffs in clarity, performance, and stack usage between the two approaches. (Outcome 3)
  3. Recognize situations where recursion risks stack overflow in C. (Outcomes 3, 7)
2. Assigned Readings

Complete before class. There is no Beej chapter for this lesson; the instructor notes are the source and they are short.

Source Sections Why
Lesson 33 supplementary notes (instructor-written) All of it The two axes, stack overflow, and when recursion wins. This is the reading.
Lesson 32 notes and widget The deferred-operation model Optional review. Today builds directly on every suspended frame holding a deferred operation.
3. Pre-Class Work
Do this first
Plan on about 20 minutes for the reading. It is short on purpose. Come ready to make a judgment call, not just to watch a demo.

Pre-Class Checklist

1
Read the Lesson 33 supplementary notes
Make sure you can answer these before class:
  • What are the two axes you weigh when choosing between a loop and recursion?
  • Why does a recursive forward traversal use O(N) stack space while the loop uses O(1)?
  • What is a stack overflow, and what does it look like in C?
  • Why can a single forward loop not print a singly linked list in reverse?
2
Recall the Lesson 32 model
In Lesson 32 every suspended recursive frame held a deferred operation, like num + ?, while it waited for the call beneath it. Today that picture explains the cost: every deferred frame is real memory on the stack. If that idea is fuzzy, replay the Lesson 32 widget.
3
Skim the In-Class section below
You will see an interactive widget that runs an iterative and a recursive version of the same function side by side. No need to use it yet; just know it is there.
4. Lesson Materials and Overview

By now you can write a traversal either way. This lesson is about choosing. The reference material below is the spine of the in-class discussion; the widget is where you see the two axes pull against each other on real code.

Jump to
Slides The Two Axes Stack Cost Stack Overflow When Recursion Wins Deciding Style

Slides

The Lesson 33 deck walks through the two axes, the stack-cost picture, the overflow demo, the case where recursion wins, and how to decide. The slides are the spine of the in-class discussion; the widget is where you practice the judgment hands-on.

Open Lesson 33 slides →

The two axes

Take any traversal you wrote recursively in Lesson 32 and you can write it as a loop instead. Both return the same answer, so correctness does not separate them. Two things do. The first is clarity: how easily the next reader can see the code is correct. The second is cost: what the code consumes on the call stack while it runs. Every recursion-vs-iteration choice is a weighing of these two.

For a function like total time, clarity is close to a tie. The recursive version reads as "this split plus the total of the rest," which mirrors how a list is defined; the loop is an ordinary accumulator that any C programmer reads at a glance. When clarity ties, cost decides.

Stack cost: O(1) vs O(N)

The iterative version keeps one stack frame and updates its variables in place, no matter how long the list. That is O(1) space on the stack. The recursive version adds a frame per element, because each call must call again before it can finish, and none of those frames can be freed until the base case at the bottom. That is O(N) space on the stack. Each of those frames holds a deferred operation, exactly the Lesson 32 picture, and each one is real memory.

// iterative: one frame, walks with a moving pointer
int total_time(const node_t *head) {
  int total = 0;
  const node_t *cur = head;
  while (cur != NULL) { total += cur->num; cur = cur->next; }
  return total;
}

Stack overflow

The call stack is a fixed region, often around 8 megabytes. As long as all live frames fit, you are fine. When they do not, the program crashes; that is a stack overflow, and in C it usually shows up as a segmentation fault before your function can return anything. A recursive forward walk over a few hundred thousand nodes will exhaust the stack and crash. The iterative version walks the same list in one frame and returns the right answer. This is the main practical reason to prefer iteration for traversals that could run long; it is not that the recursive code was worse to read.

A note for the curious: a "tail call," where the recursive call is the last thing the function does, can sometimes be optimized into a loop. C does not guarantee this, and an accumulating function like total time is not in that shape anyway. Treat deep recursion in C as a real overflow risk.

When recursion wins

If cost were the whole story you would always loop. It is not. Consider printing a list in reverse, tail first. A singly linked list has no pointer back toward the head, so a single forward loop physically cannot reach the tail first. To print in reverse with a loop you would make two passes or build your own stack of pointers. Recursion gets it almost for free:

void print_reverse(const node_t *head) {
  if (head == NULL) return;
  print_reverse(head->next);  // go to the tail first
  printf("%s\n", head->word);  // print on the way back up
}

The recursive call comes before the print, so every frame descends to the tail before anything prints, and the deferred prints fire in reverse as the stack unwinds. The call stack does the bookkeeping you would otherwise build by hand. This is the honest case for recursion, and it is the same reason free_list and collect_reverse recursed in Lesson 32.

Deciding

So the decision is never "recursion good" or "recursion bad." For a plain forward walk that might run long (length, sum, search, total), clarity ties and stack cost breaks it toward iteration: write the loop. For work the structure forces to happen tail first, recursion is clearer and more practical: write the recursion. And the cost axis only bites when the input can actually get large; a recursive function over a guaranteed small, bounded input is a perfectly defensible choice, because there clarity gets to decide on its own.

A useful habit when unsure: ask how long the input can get and whether the recursion stacks a frame per element. If the input is unbounded and the answer is yes, that is your signal to write the loop.

A note on style

No new section of the DFCS C Programming Standard is introduced today. Because these functions are short, the inline-comment guidance (§2.4) applies lightly: a comment explaining why print_reverse recurses before printing earns its place; a comment restating what an obvious loop does not. Keep naming and formatting consistent with what the tooling has enforced since Lesson 7.

5. In-Class Work

Two things to do in class. Use the checklist to track your progress.

  • Work through the recursion-vs-iteration widget below. Five guided tasks: run both versions of a function side by side, watch the stack grow and overflow, see the case where recursion wins, then make a judgment call. About 20 minutes.
  • Complete Lab 33: Splits, Two Ways. Convert three Lesson 32 traversals to iteration, keep one recursive, and meet the autograder's large-list test. Auto-graded through GitHub Classroom. Full instructions in the lab repo.

Recursion vs Iteration Walkthrough

Five tasks. Pick a function and a list length, run both versions, and weigh clarity against cost. The last task is a judgment call, not a demo.

Before you begin

Enter your name. It will appear on the completion screen so you can include it in your screenshot for the Blackboard reflection quiz.

CS210 Lesson 33 · Recursion vs Iteration: weighing the tradeoffs

Same speedrun, stored as a linked list of level splits. For each function, two versions return the same answer. They differ on two axes: how clearly the code reads, and what it costs to run. Neither axis decides on its own. The right call depends on which pressures matter for the problem in front of you.
Task 0 of 5
Two axes: clarity and cost
Current task
Loading...
Function
Splits (N)
Iterative loop

    
clarity -- --

    

      
peak frames alive: --

      

      

      
output: --

    

  

  

    
Recursive self-call

    

    
clarity -- --

    

      
peak frames alive: --

      

      

      
output: --

    

  






  

    

      
Clarity

      
Run a function to compare.

    

    

      
Cost & safety

      
Run a function to compare.

    

  

  
No version is better in the abstract. Pick a function and run both to see which pressures decide it.








  
  
  





  How this works: Pick a function and a list length, then run both versions. Every run reports two things: how clearly each version reads, and what it costs in stack frames. For a long forward walk the recursive code may read just as cleanly, yet its growing stack makes it the riskier choice in C, and at a large enough N it overflows. For tail-to-head work the recursive code is the cleaner and more practical option, because the loop would need a second pass or its own stack. The lesson is the tension, not a winner.











    

  


  
  

    
      6. After Class
    
    

      
    
        
  • Finish Lab 33 if you did not complete it in class. Submit through GitHub Classroom before Lesson 34.
    • 
        
  • Complete the Lesson 33 reflection in Blackboard: enter your widget completion code and answer the reflection prompt.
    • 
        
  • Replay the widget in free mode. Push the list length up and watch where the recursive version crashes; try both functions.
    • 
        
  • Heads up: Quiz 10 at Lesson 34 is the final quiz and covers Recursion II and III together (Lessons 32 and 33).
    • 
      

    

  


  
  

    Need help? Schedule EI with your instructor. Bring your specific code and the exact error message or output you do not understand. If your code crashes on the large list, bring the function that crashed. Specific questions get unstuck quickly.