Learning recursive programming was an eye-opener because it clearly illustrated the correspondence of programming and math (proof by induction). [Dynamic programming was meh when I learned it--memoization seems a more fitting term--as I expected to be learning metaprogramming.]
The thing I wish I'd been taught or learned much earlier is functional programming. And maybe data-oriented design if that's a name of the thing that prioritizes data schema and layers operations on them. I'm always surprised by coding-first developers not able to put fields at the appropriate place considering cardinalities, or never even think that it's important to get this right.