  With one exception, our previous work on recurrence extraction and
denotational semantics has focused on a source language that supports inductive
types and structural recursion. The exception handles general recursion via an
initial translation into call-by-push-value. In this note we give an extraction
function from a language with general recursive function definitions and
recursive types directly to a PCF-like recurrence language. We prove the main
soundness result (that the syntactic recurrences in fact bound the operational
cost) without the use of a logical relation, thereby significantly simplifying
the proof compared to our previous work (at the cost of placing more demands on
the models of the recurrence language). We then define two models of the
recurrence language, one for analyzing merge sort, and another for analyzing
quick sort, as case studies to understand model definitions for justifying the
extracted recurrences.
