3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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:

    1. Split l into l1 and l2
    2. then compute sort(l1) and sort(l2) (in either order)
    3. then compute the merge of those two results
    4. 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.

$\endgroup$
2
$\begingroup$

"Root" is being used as the thing from which everything grows, like a plant's roots. It's an allusion to the famous phrase "The love of money is the root of all evil" (1 Timothy 6:10 in the King James Bible).

I suspect that "trades description for time" means that specifying something by recursion gives a very short description at the cost of taking longer to execute, but I'm less sure of that.

$\endgroup$
  • 1
    $\begingroup$ I kind of agree, especially if you think about another perlisism (55) : "A LISP programmer knows the value of everything, but the cost of nothing." $\endgroup$ – dader Sep 11 '18 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.