11.3 - Encapsulation (2026-11-09)
Overview
Chris Bourke finishes a C exercise that loads 28 book records from a CSV into a dynamically allocated array of structures, then queries the array for the highest-rated, lowest-rated, and oldest books. He uses a countdown to introduce recursion, explains base cases and stack overflow, and shows why naive recursive Fibonacci computation repeats work exponentially before beginning an iterative alternative.
Key takeaways
- A dynamically allocated array of structures lets C programs manage collections of related records as units; determine the record count from the input file instead of hard-coding 28 when the file may change.
- Use `init_book` for an existing array element and pass its address, as in `init_book(&books[i], ...)`, when the function expects a `book *`.
- Tracking a selected array element with a `book *` avoids copying a structure whose string fields point to shared memory; access pointer members with `->` and structure members with `.`.
- A recursive function needs a stopping base case and calls that move toward it; without both, recursion can exhaust the call stack and cause a stack overflow.
- Naive recursive Fibonacci recomputes the same terms across a branching call tree, making its work exponential; an iterative loop can compute the sequence by keeping only the previous two values.
Chapters
- After a brief song, Chris Bourke resumes an exercise that loads book data using the `book` structure and its supporting functions.
- The goal is to store all 28 CSV book records in an array so the program can answer questions about the collection.
- An array declared as `book books[28]` would use fixed-size stack storage; Bourke instead allocates an array dynamically with `malloc` and `sizeof(book)`.
- Hard-coding 28 is brittle if the CSV changes; a robust version would count nonempty records first, then allocate enough structures.
- The code leaves counting records as a to-do and uses 28 for the exercise.
- The file-reading loop skips empty lines and uses an index to fill each array element with fields such as ID, title, author, and rating.
- Bourke selects `init_book` because the array elements already exist, rather than `create_book`, which dynamically allocates a book.
- He consumes the publisher token before converting the publication year with `atoi`, then passes `&books[i]` because `init_book` expects a `book *`.
- After compiling and printing the array, the output confirms records such as *Paddle Your Own Canoe* and *Death World 2* were loaded.
- The program scans the 28 books, initializes each result from `books[0]`, and updates the best or worst book when it finds a higher or lower average rating.
- Bourke changes `best_book` to a `book *` so the program tracks the selected array element instead of copying a structure containing string pointers.
- Changing the comparison field and direction finds the oldest book by publication year; the example result is *Uncle Tom’s Cabin*, published in 1852.
- He previews sorting as a way to answer multiple ordering questions, such as finding the highest-rated book at one end and the lowest-rated at the other.
- Bourke first implements a countdown from 10 with a `for` loop, then sets a challenge to print the same sequence without loops or hard-coded repeated calls.
- The recursive `countdown(n)` prints `n`, calls itself with `n - 1`, and prints “blast off” at zero.
- Each function call creates a stack frame, so the call stack tracks the countdown values that a loop would otherwise keep in an iterator.
- Bourke defines recursion as a function or process that references itself and illustrates the idea with Google’s recursive search joke and the Sierpiński triangle.
- The Fibonacci sequence starts with 1 and 1, then defines each later term as the sum of the previous two, producing values such as 2, 3, 5, 8, and 13.
- A recursive C function makes one or more calls to itself, creating additional stack frames.
- A recursive function needs a base case that stops further calls; for `countdown`, the base case is reaching zero.
- Starting at -10 without a suitable stopping condition or repeatedly calling with the same value causes runaway recursion and eventually a stack overflow.
- Every recursive call must make progress toward termination, such as reducing `n` by 1 in the countdown.
- Bourke connects recursion to loop structure: an initial call starts the process, recursive calls advance it, and the base case terminates it.
- The recursive function returns an error flag for `n < 1`, returns 1 for `n == 1` or `n == 2`, and otherwise returns `fibonacci(n - 1) + fibonacci(n - 2)`.
- Bourke uses a C `long` to hold larger results and checks examples including Fibonacci numbers 10, 11, and 12: 55, 89, and 144.
- The 50th Fibonacci calculation takes noticeably longer despite producing a result that fits in a 64-bit signed integer.
- Each non-base Fibonacci call branches into two more calls, and the tree repeats calculations such as `fibonacci(3)` multiple times when computing `fibonacci(5)`.
- For `fibonacci(5)`, the call tree includes repeated base and intermediate calculations; the growing number of calls makes the direct recursive method exponentially expensive.
- Bourke estimates that even at one billion operations per second, computing `fibonacci(100)` would take roughly 11,000 years, using the Fibonacci value as a lower-bound estimate for work.
- The recursion depth for `fibonacci(100)` is only about 100, so the main issue is excessive repeated computation rather than stack depth.
- Bourke switches back to a loop and tracks two consecutive values, then computes each next value as their sum.
- He works through variable updates in class, initially gets incorrect results, and uses a compiler warning to catch a missing return value.
- The iterative version is corrected by the end of the session, and Bourke leaves further discussion for the next class.
Transcript excerpt
0:21 When I'm walking I strut my stuff and I'm so strung out. I'm high as a kite I just might stop to check you out. Let me go wild like a blister in the sun. Let me go wild. Big hands I know you're the one. Body and beats I stain my sheets I don't even know why. My girlfriend she's at the end she is starting to cry. Let me go wild like a blister in the sun. Let me go wild. Big hands I know you're the one. When I'm walking I strut my stuff and
1:25 I'm so strung out. I'm high as a kite I just might stop to check you When I'm walking I strut my stuff and I'm so strung out. I am high as a kite I just might stop to check you Body and beats I stain my sheets I don't even >> All right, so today we're going to finish up with the exercise that we were doing where we are loading up all this book data. And now that we have the infrastructure to support a book a structure along with all of the functions that we wrote for it. It's going to be a lot easier than the first time that we did it. Instead of keeping track of all these disparate pieces of data, we're going to be able to put that into one structure.
2:13 Not only that, but instead of keeping track of a single one, I want to load up everything and put it into an array and so I can ask other questions. What's the worst book? What's the oldest book? Etc. Etc. Right? And so what I've got here I just removed all that stuff and we're going to focus on putting all those books into an
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Chris Bourke.