To me recursive thinking was more important than recursive execution of functions. For instance, I find the recursive solving of the powerset function so appealing. ... (here in scheme).
;;; power set = power {set-X} as sub (+.) {X U sub}
(define (power set)
(if (null? set)
'(())
(let ((sub (power (cdr set)))
(augment (lambda (subset) (cons (car set) subset))))
(append (map augment sub) sub))))
Seeking self-similarity often lead to tiny solutions.
Just fifty years ago, John McCarthy circulated a notice that he would be giving an informal talk that he thought would be of interest. I drove up to MIT from New Jersey to attend this seminar of typical length in a typical classroom. But the seminar was anything but typical. It was a revelation. In one session at the blackboard, John introduced Lisp—all you could do with car, cdr, cons, cond, lambda, and recursion.
Recursion had no place in mainstream programming at the time, nor did lambda calculus. Only two years before, I had sat in a coffee-room discussion of what it would mean for a subroutine to call itself. Questions raised but unanswered were whether recursive instances deserved to be deemed the "same" subroutine, and, if you could do it, what good would it be? It turned out you could do it: I programmed it for the IBM 704. Given the challenge, the now standard stack solution arose inexorably. But the question of what it was good for remained.
In the course of the lecture John introduced the usual basic list functions like copy, append and reverse (quadratic and linear), as well as tree manipulation. He went on to higher-level functions, demonstrating maplis and lambda. By the end of the hour he had put together a powerful little toolkit of functions which he used in his finale: symbolic differentiation of univariate expressions.
There it was—functional programming ex nihilo. McCarthy acknowledged IPL V and recursive function theory, but the elegant and practical face he put upon these antecedents was a work of genius. Nobody would ever again wonder what good it was to allow functions to call themselves. And it was all so clear one could go home and build it oneself without any instruction book.
- Doug McIlroy
Same here, but a quick google search always bring up McIlroy comment. If you find it, submit it on HN :)
ps: there's a post on Recursion in early languages https://news.ycombinator.com/item?id=8073361 that mentions McCarthy indirect influence on the ALGOL comitee, but nothing else.
I completely agree. Whenever I praise recursion there's always some person that's shouts "Recursion is just looping!" These people completely miss how recursion changes how you codify problems. You get to break the problem down into a sub-problem which leads to much more expressive code. Combine recursion with pattern matching for extra spicy solutions.
I'm the same way. I view recursion best as a way to use induction in functions. If this is true, and this with a small change is true, then keep on going....
I first embraced recursion back in university when I realized that in certain situations, memory could "automatically" be allocated and deallocated by using the stack (Which is a nice short cut when learning C).
In time, this lead to an appreciation of recursion in terms of dynamic programming and code clarity. But I still believe that the best way to teach recursion is through appealing to students' lazy tendencies.
