I will add one important point not addressed in other answers so far: I consider that rejection criteria for a journal to be different from that for a conference, even for the same article. The most pertinent point I see here is that whereas journal articles have the time to request multiple rounds of revision (which could drag on to a year or two or even longer), conference reviewers must decide immediately whether the article can be quickly made acceptable, or not, since the conference review and presentation timeline is always very tight. In journal submission terms, a conference submission can give only one of two decisions: either it is "accept with minor revisions", or it is "reject". In particular, there is no option for "major revisions" as a decision.
With this understanding, the question is: whatever the revisions you think might be necessary, can they be done easily and feasibly in the space of just a couple of weeks? If so, you can accept the article and request those minor revisions. But if the revisions you consider essential cannot be done easily or quickly (in the timeframe of the conference, specifically, before the deadline for authors to submit the final "camera-ready" proofs), then you should recommend rejection.
Note that my answer is very general and does not even address your substantial question of whether or not the absence of a literature review is sufficient to reject the article. Rather, I ask you to reframe the question thus: do you have confidence that, in the tight timeframe of the conference, the authors can fix the literature review problems? Also, note that, unlike with a journal submission, you probably will not be given the opportunity to verify if they have done what you consider essential.
With this understanding, based on the details in your question, I think it might be unlikely that the authors would satisfactorily reframe the article in the literature, especially since you would not be able to verify this. If so, you should probably recommend a rejection. But, of course, explain to the authors what you would have like to see, so that they can hopefully do the revisions and submit to another conference or to a journal.