Recursion Is A Win Iteration A Low-level Implementation Artifact (RIAWIALIA)

"If in its continual development mathematics seldom if ever attains
a finality, the constant growth does mature some residue
that persists. But it is idle to pretend that what was good
enough for our fathers in mathematics is good enough for us,
or to insist that what satisfies our generation must satisfy the
next."
                                                                                                                                                                                                   Eric Temple Bell
                                                             "The Development of Mathematics"
                                                                       McGraw-Hill Book Company
                                                                   New York London 1945, p.172

My generation whether satisfied or not, had only FORTRAN to program digital computers. And it took away the natural mathematical thinking based on equivalences and implications. Equal to sign ('=') is used to change the bit pattern stored in memory. A DO loop is necessary to calculate a recursive function like factorial. Recursion is forbidden because it can not be efficiently implemented. FORTRAN simply did not allow recursion until 90's.

In the late 80's I found PROLOG, a language with no assignment statement and no iteration. Recursion is the norm to get any work done. That indeed is programming in logic far from formula translation into assignments and loops.

It is known in computing circles that recursion is expressive, elegant and conducive to increase in programmer productivity.

Jon Bentley  in his 1982 book "Writing Efficient Programs" informs us that

"Recursive procedures(that is, procedures that can call themselves) are powerful expressive tools that can greatly ease the design and implementation of a correct program. That lesson was made clear to me when I translated a nineteen-step iterative algorithm that I had written (which resulted in over 100 lines of code and took two twelve-hour days to debug) into a four-step recursive algorithm (which took less than 30 lines of code and took less than an hour to implement). Unfortunately, this expressive power is not without cost, because many implementations of recursion are slow."

Wow! 20 times increase in  productivity. Definitely Recursion is a win.

No wonder PROLOG programmers pity FORTRAN foot soldiers.

Jon Bentley in 1998 after some experimentation with C compilers:

"These little experiments have illustrated some big truths about recursion.

• Recursion is expressive. Some of the recursive tree functions are much clearer than their iterative cousins.
• Recursion can be very expensive.
• Tail recursion is sometimes cheap. Smart compilers convert it to iteration.
• Tail recursion is sometimes very expensive. Converting it by hand to iteration can be very effective.
• Guarding recursive calls can be effective.
• Handwritten stacks require lots of code yet yield little (if any) run time benefit. (Guy Steele said it best: "If the programmer can simulate a construct faster than the construct itself, then the compiler writer has blown it badly.")
• Optimization is usually effective. Enabling compiler optimization can make some little functions an order of magnitude faster. Then again, it makes some functions a bit slower.
• Timing is hard. The factor of 20 in a conditional expression is just one of many mines in this very large field."

I was a little disappointed after reading this because conditional expression is one of my favorite constructs in imperative languages like C and Java. 

In 2008 book "Beautiful Code", a collection of articles, It is  Brian Kernighan saying " recursion is a win. This fundamental programming technique almost always leads to smaller, cleaner, and more elegant code than the equivalent written with explicit loops, and that is the case here. The idea of peeling off one matching character from the front of the regular expression and from the text, then recursing for the rest, echoes the recursive structure of the traditional factorial or string length examples, but in a much more interesting and useful setting."

In the second decade of 21st century, compiler technology has improved to the extent that functional calls are pretty cheap making recursion a viable technique even in imperative languages like C, Java etc.