* HN and classic Reddit sort their items on a single dimension ("hotness"), calculated using a few input variables and producing a single output variable. This is about as cheap to calculate as recommendation systems get. The XKCD comment recommender is a bit more complex, but still in the same complexity class. Since the whole point of an algorithm like this is to be timely, the naive approach is to compute it on-the-fly, which it's perfectly simple enough to manage.
* At a somewhat more complex level, you get stuff like a basic, uncustomized Similar Items list. If YouTube has no data on you, this is what you get from their sidebar recommender (and their front page would be analogous to Reddit and HN, but sharded by region and language). It's also pretty close to what AdWords used to be, before they started doing user profiling. The thing with this method is, even though it involves some level of AI, it's presenting the same thing to everyone and it's expensive, so the natural solution is to precompute it.
* Personalized recommenders are the worst of both worlds. You can't naively compute it on-the-fly, because it's too slow, but you also can't naively precompute it, because there's a combinatorial explosion of users and items. You actually have to be clever about it.