Skip to content
DoingCamp CS

Make it comfy

Lesson style

Quick mode shows the key picture, a summary and the practice. Good for a refresher.

Theme
Font

Both fonts are designed to be easy to read. Some readers with dyslexia prefer Lexend.

Text size
Spacing
Animations

F03

Programming 2: Abstraction & Recursion

“Russian nesting dolls that open themselves”

Lessons

Start the course →0 of 20 lessons done
  1. Functions are valuesFreeIn Python a function is a value, just like a number. You can store it in a variable, put it in a list, and pass it to another function. Functions that take functions are called higher-order functions. · 14 min
  2. Functions that make functionsFreeA function can build and return a new function. The new function remembers the variables from where it was made (a closure). lambda writes small functions in one line. · 15 min
  3. Environments: where names liveFreeEvery name lookup follows a chain of frames, starting where the code is running and moving outward. This environment model explains scope, closures and nonlocal precisely. · 15 min
  4. Recursion🔒 MembersA recursive function solves a problem by calling itself on a smaller version of the same problem, until it reaches a case so small the answer is obvious. · 15 min
  5. Thinking recursively🔒 MembersThe trick to writing recursion is the "leap of faith". Assume your function already works on smaller inputs, and only figure out how to use that answer. It works on strings and lists, not just numbers. · 15 min
  6. Tree recursion🔒 MembersWhen a function calls itself more than once, the calls branch out like a tree. It's perfect for exploring choices ("take it or leave it"), but it can repeat a lot of work. · 16 min
  7. Processes and growth🔒 MembersTwo functions can give the same answer but run very differently. Some build up deferred work, some carry the answer along, some repeat work. Memoization and smarter recursion can turn an impossible computation into an instant one. · 15 min
  8. Sequences: map, filter, reduce🔒 MembersMost work on lists follows three patterns. Transform every item (map), keep some items (filter), combine everything into one value (reduce). Chain them like an assembly line. · 14 min
  9. Data abstraction🔒 MembersBuild new kinds of data from a few functions, constructors to make it and selectors to read it, and let the rest of the program use only those. Then you can change how the data is stored without breaking anything. · 15 min
  10. Trees as data🔒 MembersA tree is a value with branches, and each branch is a smaller tree. Because trees are built from trees, recursion is the natural way to work with them. · 16 min
  11. Linked lists🔒 MembersA linked list is a chain of links, each holding one value and a pointer to the rest of the chain. It's the simplest recursive data structure, and the shape behind lists in Scheme and many other languages. · 15 min
  12. Mutation and state🔒 MembersSome values change over time. State makes programs remember things, like a balance or a score, but it also means the same call can give different answers. Understanding identity vs equality keeps mutation safe. · 15 min
  13. Iterators and generators🔒 MembersAn iterator hands out values one at a time, only when asked. Generators make iterators with yield, so you can work with sequences too big (or infinite) to store all at once. · 15 min
  14. Objects and classes, deeper🔒 MembersAn object bundles state with the functions that change it. Class attributes are shared by every instance, instance attributes belong to one object, and methods are just functions that get the object as self. · 15 min
  15. Inheritance and special methods🔒 MembersSpecial methods with double-underscore names let your own classes work with Python's built-in syntax, like printing, +, ==, len() and for loops. Combined with inheritance and shared interfaces, different objects can be used the same way. · 16 min
  16. Efficiency and orders of growth🔒 MembersHow a program's time and memory grow with its input matters more than raw speed. Θ notation names the growth rate, and a few common growth classes cover almost everything you'll meet. · 16 min
  17. Functional programming and immutable data🔒 MembersFunctional programming builds programs from pure functions and data that never changes. Instead of editing values, you make new ones. It makes code easier to test, reason about and run in parallel. · 15 min
  18. Meet Scheme🔒 MembersScheme is a tiny, elegant language where everything is written in parentheses. With almost no syntax to learn, you can see the ideas of this course (functions, recursion, lists) in their purest form. · 16 min
  19. Interpreters🔒 MembersAn interpreter is a program that runs other programs. It reads text into tokens, parses the tokens into a tree, and evaluates the tree, using eval and apply calling each other. · 18 min
  20. Boss level: your own tiny language🔒 MembersBuild a working programming language, with variables, if, functions, recursion and closures, in about 80 lines of Python. It uses every big idea from this course. · 50 min

💼 Already know this course?

Placement tests are coming soon. Until then, you can mark it as known so it’s colored in on your map. You can undo this any time.