As a Common Lisp programmer I think in mappings and tail recursion and I dislike using the loop construct. Sometimes loop is still the best solution but it's not as elegant.
As a Common Lisp programmer I think in mappings and tail recursion and I dislike using the loop construct. Sometimes loop is still the best solution but it's not as elegant.
The canonical recursive example is factorial, but a better example for "easier" is quicksort. Quicksort is inherently recursive and it cannot be expressed without a stack, while factorial is not inherently recursive and is easy to express as a loop.
That's not to say you can only write Quicksort in a recursive language; I've seen Quicksort implemented in old versions of Fortran for example that had no notion of recursion. But since the algorithm is inherently recursive, if you write it in a non-recursive language you have to manually build a stack to keep track of your progress. This makes Quicksort in a non-recursive language require many more lines of code and be much harder to understand.
Having said all that, I'm not going to type a full implementation of Quicksort into an HN comment. Instead, here's factorial three ways in Common Lisp. I think rfact and trfact are clearer than lfact. You might disagree.
(defun lfact (n)
"Uses looping to compute n! No stack required."
(let ((result 1))
(loop for i from 2 to n
do (setf result (* result i)))
result))
(defun rfact (n)
"Uses ordinary recursion to compute n! Requires n stack frames,
which is bad unless you know n will always be small."
(declare (optimize (debug 3))) ;; tell the compiler not to optimize away the name, in case you want to trace rfact
(if (< n 2)
1
(* n (rfact (- n 1)))))
(defun trfact (n &optional (accum 1))
"Uses tail recursion to compute n! No stack required."
(declare (optimize (debug 1))) ; ensure tail call elimination
(if (< n 2)
accum
(trfact (- n 1) (* accum n))))