[wmf]

Automata and regular languages, invariants and proofs, functional programming, recursion come to mind immediately.

(Note that I'm not interested in bikeshedding about how a small fraction of highly motivated programmers have learned these things outside of formal education.)

[SamReidHughes]

Recursion should be off that list, or at least it takes "necessarily" to a farther percentage than anything else here. Tons of engineers teach themselves that independently. In high school.