I learned recursion in Sunday School, although I didn't realize that until many years later.

For recursion is implicit in the "begats" of the Fifth Chapter of Genesis in The Bible. Adam begat Seth; Seth begat Enos; Enos begat Cainan; Cainan begat Mahaleel; Mahaleel begat Jared; Jared begat Enoch; Enoch begat Methusaleh. (And, as Sportin' Life sings, in the Gershwins' opera, Porgy and Bess, "Methusaleh lived nine hundred years. But who calls that livin when no gal will give in to no man who lived nine hundred years?")

Take B(_) as the begat-function. Thus, B(Adam) = Seth; B(Seth) = Enos, or B(B(Adam)) = Enos. Then, B(B(B(B(B(B(B(Adam))))))) = Methusaleh, the 7th generation begat from Adam.

(In the Broadway musical Finian's Rainbow -- later made into a Coppola film staring Fred Astaire -- one of the songs of E. Y. Harburg and Burton Lane was "Begin the Begat" song, announcing, "They begat the misbegotten GOP!")

Of course, I modeled the begat-function after ARITHMETIC's successor-function, wherein S(_), where S(n) = n + 1, that is, the successor of number n is number n and one more. Thus, S(0) = 1; S(1) = 2, or (embedded) S(S(0)) = 2. Thus, S(S(S(S(S(S(S(0))))))) = 7. The 7th successor of 0 is 7, just as Methusaleh is the 7th begat of Adam.

We can show that COUNTING and THE NATURAL (COUNTING) NUMBERS ARE GENERATED RECURSIVELY. That ADDITION IS RECURSION ON COUNTING; that MULTIPLICATION IS RECURSION ON ADDITION; that EXPONENTIATION IS RECURSION ON MULTIPLICATION. Thus, THE PRIMARY OPERATIONS OF ARITHMETIC ARE DEFINED RECURSIVELY. (You also encounter recursion in compound interest on your Savings Account. And, in general, RECURSIVE FUNCTION THEORY.) See! See! NATURAL NUMBER ARITHMETIC GENERATED BY RECURSION.

RETURN TO GENERATING ARITHMETIC