I can't presume to speak for Perlis, but my intuition is as follows:
Recursion is descriptive
Especially at the time this was written, the specification of a recursive function seems much more descriptive than prescriptive, in the sense that a recursion describes a mathematical property we want the result to satisfy, rather than a series of computation steps. E.g. for mergesort
sort(l) = let l1, l2 = split(l) in merge(sort(l1), sort(l2))
Recursion involves a notion of time
But obviously recursion also describes a process or series of steps. In the case of mergesort:
- then compute
sort(l2) (in either order)
- then compute the
merge of those two results
- the result of this is the value we wished to compute
This suggests that the time taken by this computation is the time of each of these individual steps, which itself involves a recursive equation (over integers) to compute, namely the time taken to sort the sublists
Trading description for time is the essence of computation
One way of characterizing computation is that we want to go from an abstract mathematical "timeless" description of an object to a concrete representation which can be manipulated symbolically.
Computation can be defined as the process which goes from the abstract to the concrete, and the time which this process takes is one of the central considerations of CS as a field.
My last advice is that sometimes it is important not to overthink epigrams or koans, but let understanding come naturally with experience.