Alan Perlis Epigram on Recursion

So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis:


Recursion is the root of computation since it trades description for time.


-- Alan Perlis

Common to epigrams, this sounds like a deep insight. But I've already got stuck on "root of computation" and in which sense recursion "trades description for time".

Any explanation would be nice. : )

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:

• Split l into l1 and l2

• then compute sort(l1) and 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 l1 and l2.

-
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.

StackExchange Computer Science Q#91974, answer score: 5