3 ms·

Can you provide a concrete example of an algorithm that’s easier to express with recursion?

dreamcompiler 3y ago
"Easier" is in the eye of the beholder. To anyone trained entirely in imperative languages, recursion will always seem foreign and thus harder. But to someone familiar with functional programming, recursion is often easier to understand. 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))))

"Easier" is in the eye of the beholder. To anyone trained entirely in imperative languages, recursion will always seem foreign and thus harder. But to someone familiar with functional programming, recursion is often easier to understand. 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))))