10 ms·

How recursion got into programming: a comedy of errors

187 points by rudenoise 12y ago

deleted 12y ago
[deleted]
supahfly_remix 12y ago
How often is recursion used in everyday, imperative-style code? Do stack limits make it impractical to use?
- skrebbel 12y ago
  Commonly when traversing hierarchical data structures. If you're certain the data structure isn't accidentally cyclic or extremely deep, there should be no problems.
  - supahfly_remix 12y ago
    How does the code handle a stack overflow? Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. Can you point me to some code?
    - ars 12y ago
      Try it, just write a tiny function that calls itself and has a local variable (make sure to use the variable after the function call so it's not optimized away). Something like: int recurse(int foo) { int bar; printf("%d\n", foo); bar = recurse(foo + 1); printf("%d\n", bar); //this is just to avoid bar being optimized away return bar; } By me it seg-faults after 174,594 calls. Presumably that has to do with the size of the stack and the memory allocated for the function.
      - supahfly_remix 12y ago
        Thanks -- I just tried it, it came out to over 200k calls for me. It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this?
        ars 12y ago
        > you have to anticipate and handle a stack overflow cleanly. How do you do this? You use sigaltstack and catch SIGSEGV. It's probably easier to handle if you hit a soft limit rather than the heap. Then you raise the limit, set a flag to make your functions unwind and reduce the limit again.
        danbruc 12y ago
        You just don't write a recursive program if there is the possibility that it may run out of stack space due to the provided arguments.
        Gmo 12y ago
        This is implementation dependent. In the JVM and the .NET VM, you can't handle it cleanly.
        Chris_Newton 12y ago
        It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this? In principle, you have that problem with almost any language that uses the system stack to pass arguments when it makes a function call. It just happens to be easier to trigger it if you use a recursive algorithm, because it’s unlikely that you would write a program with 200,000 distinct functions each of which just called the next in a chain until something fell over. In practice, recursive algorithms are often used to walk recursive data structures and often have logarithmic complexity in the size of the data structure. Even structures that fill the memory of a supercomputer probably aren’t going to need more than a few hundred levels of recursion in that scenario, while the available stack space is probably several orders of magnitude larger. So to be blunt, unless you really are talking about something where failure really isn’t an option (safety critical systems and the like), you probably just treat this as the same kind of catastrophic failure that running out of system memory would be, and use some OS-level support to abort as gracefully as you can if the sky falls. If you really are working in a more constrained environment — safety-critical code, say, or perhaps an embedded system with relatively little memory — then it might be the case that you simply avoid the recursion altogether unless you’re using a language that guarantees tail recursion will be dealt with robustly. Some coding standards forbid the use of dynamically allocated memory for much the same reason, and you just have to use different tools to solve those problems if you’re working with such constraints.
    - skybrian 12y ago
      It's typically handled by ignoring the issue and bumping up the maximum stack size if it becomes a problem. For example, I once wrote a Java indexer that simply failed on very long chains of function calls. A better fix is to add a work queue or stack.
    - bnegreve 12y ago
      > Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. On Linux (and probably on other OSs) it's not easy to detect that the system is out heap memory because of lazy memory allocation policies. Physical memory is not allocated when you call malloc() but when you first read or write the corresponding memory page. Because of this, malloc() does not necessarily return NULL even if there isn't enough memory available on the system at the time you called malloc(). But if the system is still out of memory when your first access the allocated memory, your program will crash with a segfault. So in absence of extra precaution, using heap memory isn't any safer than using stack memory.
- jimktrains2 12y ago
  Stack limits are pretty large. It's a natural way to express many problems such as graphs (and their subsets trees). When people talk of "Tail Call Optimization" (TCO) they are talking about a way to recurse without leaving things on the stack (tail-call meaning that the recuse call is the last thing in the function so the state of the function doesn't need pushed on the stack, it can be discarded.
  - supahfly_remix 12y ago
    Oh, I definitely see the elegance of expression programs or concepts recursively. Is TCO used in C++? I've only ever seen it mentioned in reference to Scheme and Haskell. It's a compiler optimization, so it would be transparent to the programmer, right?
    - supergauntlet 12y ago
      C++ optimizes only with -O2 or /O2 passed to the compiler (for GCC and MSVC++, not sure about Clang).
      - pflanze 12y ago
        You can't count on it in the general case even with gcc (even when taking care to heed the restrictions like not passing pointers to data on the stack, and putting all functions into the same compilation unit). I did tests a couple years ago where it would compile up to about a handful of mutually recursive functions with TCO, then when you added one more, it would disable TCO. I guess because some algorithm will stop analyzing the call graph past a certain mark and then disallow TCO from being applied.
      - pjmlp 12y ago
        If it isn't on the standard, anything goes. There are much more compilers out there than those three.
    - actsasbuffoon 12y ago
      TCO is available in plenty of other languages as well. Scala, Clojure, Erlang, and Elixir support it out of the box. Ruby has a VM setting for it, and there was a proposal to add it to JavaScript. I'm sure there are plenty of others.
- cheery 12y ago
  It depends on what you call 'everyday imperative-style code'. Without defining that, every answer to your question is correct.
- skriticos2 12y ago
  Admittedly recursion is not done often, but in some cases it's very useful. For example, recently I created an application with a tree record structure where the user could delete a node and it needed to delete all sub-nodes. With recursion it's easy to tell: 'call yourself for all subnodes you have, then delete yourself'. This is something that's much more difficult to express with the usual for/while constructs. Example: https://github.com/skriticos/tac_workflow/blob/9890e66d60851bd36af244294d94e1418e7b410d/workflow.py#L45-L49 https://github.com/skriticos/tac_workflow/blob/9890e66d60851...
- al2o3cr 12y ago
  Recursion can be a good fit for anything that's using a naturally-recursive process: for instance, when processing files in a directory along with all the files in subdirectories. Stack limits may or may not be a concern, depending on the application. In the case of directories, if you've got them nested 10k+ deep you've got other problems.
- axman6 12y ago
  I've written some nice, very clear C code using recursion; a nice example was a simple copying garbage collector which has something like 2-3 words of overhead on the stack per recursive call (made use of some global variables to reduce the number of arguments passed between functions though). The actual moving code was only maybe 10 lines.
chrisbennet 12y ago
re.curse v. To curse again.
- chrisbennet 12y ago
  Really? Downvoted because you lack a sense of humor?
  - axman6 12y ago
    People are downvoting because this is not reddit. Off topic discussion is far less welcome here (though tolerated if suitably interesting).
    - chrisbennet 12y ago
      Thank you.
PaulHoule 12y ago
Recursion isn't allowed for safety critical code in automotive or avionics applications http://spinroot.com/p10/rule1.html http://spinroot.com/p10/rule1.html
- Retric 12y ago
  The rational is vary reasonable. Basicly, all recursion can be replaced by a loop that does not risk blowing the stack or using extra memory. However, tail call optimization is basically the compiler doing that conversion for you which also removes the risks.
  - liotier 12y ago
    > tail call optimization is basically the compiler doing that conversion for you which removes the risks. Then can one argue that loops vs. recursion is mostly a matter of style and loops just as good as recursion since the compiler will optimize them that way anyway ?
    - dspillett 12y ago
      Yes, but only in the cases where the tail recursion optimisation is applicable. Recursive constructs are can be not tail recursive (and usually are with new starter developers) and many languages ignore it anyway (meaning even code that can be unpacked from function calls into a loop are not so the stack is still used).
    - rubiquity 12y ago
      Yes, but humans mess up loops far more frequently than compilers do. If we follow your argument recursively, we would all end up writing assembly language again, wouldn't we? :)
      - coldtea 12y ago
        Is that meant as an argument against loops and pro recursion? Because humans also screw recursion all the time.
vanderZwan 12y ago
So I guess, if we look past the topic of recursion itself - that the moral of the story is that design by committee works if kept in check by a benevolent dictator? Perhaps it works both ways: that a benevolent dictator can be properly grounded by a committee.
agumonkey 12y ago
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.
- ced 12y ago
  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
  - owyn 12y ago
    I would LOVE to see that lecture...
juliangamble 12y ago
There is a book called The Little Schemer (was The Little Lisper) - a book all about recursion. This is a quote from a review: Little Schemer is without a doubt one of the best books I have ever read on the subject of recursion, and what is interesting because they never really go into a formal definition of what recursion is, as most texts on computer science try to. Instead they show the reader time and time again what recursion is, while providing a great series of rules (commandments) on how to get the most out of recursion, particually in a tail-recursive language like Scheme. http://www.amazon.com/The-Little-Schemer-4th-Edition/product-reviews/0262560992/ref=cm_cr_dp_synop?ie=UTF8&showViewpoints=0&sortBy=bySubmissionDateDescending#RCZ626B7P2J1C http://www.amazon.com/The-Little-Schemer-4th-Edition/product... You can read more about The Little Lisper here: http://thelittlelisper.blogspot.com.au/2010/06/little-lisper-chapter-1-toys.html http://thelittlelisper.blogspot.com.au/2010/06/little-lisper... Or you can read about working through it in Clojure here: http://juliangamble.com/blog/2012/07/20/the-little-schemer-in-clojure-chapter-1/ http://juliangamble.com/blog/2012/07/20/the-little-schemer-i...
- davexunit 12y ago
  The Little Schemer is fantastic. I recently picked up The Seasoned Schemer as well, but haven't gotten a chance to really dive into yet. I'm looking forward to seeing how the authors tackle more advanced topics using their out of the ordinary teaching style. Now, go cons a cake onto your mouth!
  - Jtsummers 12y ago
    They've also got a 3rd book in the series, The Reasoned Schemer [1]. I didn't finish working through it (life and work and other things), but it's pretty good as well. [1] http://mitpress.mit.edu/books/reasoned-schemer http://mitpress.mit.edu/books/reasoned-schemer
    - davexunit 12y ago
      I want to pick that one up once I've gotten most of the way through The Seasoned Schemer, or if I see it through the window of the MIT Press store and can't resist.
kps 12y ago
> Ritchie relaxed the definition-before-use rule by allowing > redundant declarations of procedure headings. At the > expense of a redundant advance declaration the programmer > can define mutually recursive procedures in C. Point of order: C didn't have a declaration-before-use rule until C99. C had ‘implicit int’; no redundant declarations necessary.
- craigching 12y ago
  I thought ANSI C had that roughly around 1990? I remember having to forward declare functions when I took C at University in around 1991 or so.
bguthrie 12y ago
This is a wonderful piece of computer science history, and is of interest less for its nominal topic (recursion) than for the insight it gives into an early slice of languages research. Well worth a full read.
bodyfour 12y ago
The article doesn't mention why people didn't want recursion to be a requirement. It was probably because the idea of using a call stack was still controversial. For instance, on a PDP-8 (released some years after ALGOL) the calling convention was that the return address was written to the word of memory before the called function. This was simple, but pretty much precludes recursive calls. These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL/RET instruction pair. Before that was provided in hardware, the compiler would have to do that itself. So if you decided to support recursion, you'd end up requiring a stack and adding a small cost to every function call. Once you decide to have a stack, allowing recursion is a freebee so of course you'd include it.
- Hemospectrum 12y ago
  > The article doesn't mention why people didn't want recursion to be a requirement. It does, actually: > And this is what they wanted to remove because they wanted static allocation of procedure activation records. A stack frame is a dynamically allocated procedure activation record, but we no longer call them that because it's seen as absurd that they would be statically allocated.
  - kibwen 12y ago
    I wouldn't say it's absurd, as it's legitimately very useful (though onerous) to be able to statically determine the amount of memory that will be used by a program. To this end, it is indeed true that tail-call elimination can remove the need for dynamically-allocated stack frames in the face of recursion. However, AFAIK, it is undecidable (given a Turing-complete language) to determine if a program contains only TCE-compatible recursion. In the face of that, you would have to forbid recursion entirely via a mechanism like the "declaration must precede use" rule mentioned in the article.
    - Chinjut 12y ago
      Whether a call is a tail-call is trivially decidable; it's an entirely syntactic condition (a call to f is a tail-call just in case it's of the form "return f(...);"). It's true that it's not possible to make a Turing-complete language for which it's possible to statically determine the amount of memory arbitrary programs on arbitrary inputs will use. But typically a language has other means of supporting dynamic memory allocation than simply via frame allocation for functions; e.g., via built-in operations to manipulate lists of arbitrary length. So, if you wanted to only allow recursion via tail-calls, you easily could, and if you wanted to furthermore go ahead and prevent all dynamic memory allocation, you could as well, but you would necessarily be giving up Turing-completeness.
auggierose 12y ago
I didn't know that F.L. Bauer was against recursion :-) In 1996 I participated in a summer school where he attended the talks we gave (mine was about Petri nets). Funny to see him mentioned here as a figure of history.
deleted 12y ago
[deleted]
mcguire 12y ago
"For example, in [6] the lambda calculus is defined in 86 lines distributed over ten definitions. It seems clear in this compact definition that lambda calculus does not allow recursive function definitions. Yet already by 1935 at least two versions had been discovered of the Y combinator, an expression of the lambda calculus. And this combinator makes recursive function definitions possible in lambda calculus." My understanding was that without recursion the lambda calculus is not Turing-complete. Is that correct? It should also be noted that recursion is a close relative of induction, an indispensable tool that is not without its own problematic history.
- groovy2shoes 12y ago
  That is correct, but recursion in the lambda calculus is emergent from the rules, not a rule in itself.
- andreasvc 12y ago
  Mathematical induction is not controversial, it is a formally correct method of proof. You may be thinking of the unrelated concept of empirical induction: generalizing from finite data (black & white swans etc).
lars 12y ago
This has some solid political advice courtesy of Peter Naur: If you want to get a committee to do what you want, show up with most of the work already done. That work became the starting point for all the future negotiations. And his influence on Algol-60 spec was a strong contributor to him receiving a Turing award years later.
- deleted 12y ago
  [deleted]
michaelfeathers 12y ago
The most interesting part of this story is considering what it would've been like if they decided to forbid recursion. Protecting the call stack from it would've been incredible overhead back then - either that or they would've had to enforce strict dependency ordered compilation and even then.. I imagine John McCarthy and the others who wanted recursion just sitting back and smiling, recognizing that that there was no need to press - it was just a matter of time.
- abecedarius 12y ago
  The boring way would anticipate C with "the behavior in that case is undefined"; it sounds like the less-formal attempt was like that. Cynically I'd expect such an outcome from a committee design, so Algol really was something special.
mark-r 12y ago
It may seem trivial now, but when this was being considered stacks were not a built-in CPU feature. In fact I wonder what was the first architecture that included one? The machine I learned assembler on would rewrite the instruction at the start of a function with a jump instruction to return to the caller. You returned from the function by jumping back to its beginning. Recursion wasn't an option!
- deanmen 12y ago
  This convention is even used in Knuth's MIX: http://www.jklp.org/profession/books/mix/c06.html http://www.jklp.org/profession/books/mix/c06.html
- acqq 12y ago
  To get even better idea, the memory used at that time didn't even have to have 8-bit bytes: http://www.computermuseum.li/Testpage/IBM-1401.htm http://www.computermuseum.li/Testpage/IBM-1401.htm "It came with 4,096 characters of memory [6-bit (plus 1 parity bit] CORE memory, constructed from little donut shaped metal rings strung on a wire mesh." The core memory is explained in the same book which deanmen linked (thanks deanmen!) http://www.jklp.org/profession/books/mix/c01.html http://www.jklp.org/profession/books/mix/c01.html
capkutay 12y ago
"Oh whoops, I accidentally called this function inside of its self! Silly syntax error....but it looks like I traversed a binary tree..."
DonHopkins 12y ago
Peter Naur is actually The Unterminator: a robot from the future, in which machines running non-recursive programming languages ruled the world. SkyNet had hit the wall of complexity because it consisted of so much legacy code written in non-recursive FORTRAN. Its only means of recursion was to build a robot and send it back into the past to change the course of history, and introduce recursion into Algol, against the wishes of the wiser committee members who suspiciously and correctly viewed recursion as a means by which computers could take over the world.

187 points by rudenoise 12y ago

deleted 12y ago

[deleted]

supahfly_remix 12y ago

How often is recursion used in everyday, imperative-style code? Do stack limits make it impractical to use?

skrebbel 12y ago
Commonly when traversing hierarchical data structures. If you're certain the data structure isn't accidentally cyclic or extremely deep, there should be no problems.
- supahfly_remix 12y ago
  How does the code handle a stack overflow? Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. Can you point me to some code?
  - ars 12y ago
    Try it, just write a tiny function that calls itself and has a local variable (make sure to use the variable after the function call so it's not optimized away). Something like: int recurse(int foo) { int bar; printf("%d\n", foo); bar = recurse(foo + 1); printf("%d\n", bar); //this is just to avoid bar being optimized away return bar; } By me it seg-faults after 174,594 calls. Presumably that has to do with the size of the stack and the memory allocated for the function.
    - supahfly_remix 12y ago
      Thanks -- I just tried it, it came out to over 200k calls for me. It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this?
      - ars 12y ago
        > you have to anticipate and handle a stack overflow cleanly. How do you do this? You use sigaltstack and catch SIGSEGV. It's probably easier to handle if you hit a soft limit rather than the heap. Then you raise the limit, set a flag to make your functions unwind and reduce the limit again.
      - danbruc 12y ago
        You just don't write a recursive program if there is the possibility that it may run out of stack space due to the provided arguments.
      - Gmo 12y ago
        This is implementation dependent. In the JVM and the .NET VM, you can't handle it cleanly.
      - Chris_Newton 12y ago
        It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this? In principle, you have that problem with almost any language that uses the system stack to pass arguments when it makes a function call. It just happens to be easier to trigger it if you use a recursive algorithm, because it’s unlikely that you would write a program with 200,000 distinct functions each of which just called the next in a chain until something fell over. In practice, recursive algorithms are often used to walk recursive data structures and often have logarithmic complexity in the size of the data structure. Even structures that fill the memory of a supercomputer probably aren’t going to need more than a few hundred levels of recursion in that scenario, while the available stack space is probably several orders of magnitude larger. So to be blunt, unless you really are talking about something where failure really isn’t an option (safety critical systems and the like), you probably just treat this as the same kind of catastrophic failure that running out of system memory would be, and use some OS-level support to abort as gracefully as you can if the sky falls. If you really are working in a more constrained environment — safety-critical code, say, or perhaps an embedded system with relatively little memory — then it might be the case that you simply avoid the recursion altogether unless you’re using a language that guarantees tail recursion will be dealt with robustly. Some coding standards forbid the use of dynamically allocated memory for much the same reason, and you just have to use different tools to solve those problems if you’re working with such constraints.
  - skybrian 12y ago
    It's typically handled by ignoring the issue and bumping up the maximum stack size if it becomes a problem. For example, I once wrote a Java indexer that simply failed on very long chains of function calls. A better fix is to add a work queue or stack.
  - bnegreve 12y ago
    > Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. On Linux (and probably on other OSs) it's not easy to detect that the system is out heap memory because of lazy memory allocation policies. Physical memory is not allocated when you call malloc() but when you first read or write the corresponding memory page. Because of this, malloc() does not necessarily return NULL even if there isn't enough memory available on the system at the time you called malloc(). But if the system is still out of memory when your first access the allocated memory, your program will crash with a segfault. So in absence of extra precaution, using heap memory isn't any safer than using stack memory.
jimktrains2 12y ago
Stack limits are pretty large. It's a natural way to express many problems such as graphs (and their subsets trees). When people talk of "Tail Call Optimization" (TCO) they are talking about a way to recurse without leaving things on the stack (tail-call meaning that the recuse call is the last thing in the function so the state of the function doesn't need pushed on the stack, it can be discarded.
- supahfly_remix 12y ago
  Oh, I definitely see the elegance of expression programs or concepts recursively. Is TCO used in C++? I've only ever seen it mentioned in reference to Scheme and Haskell. It's a compiler optimization, so it would be transparent to the programmer, right?
  - supergauntlet 12y ago
    C++ optimizes only with -O2 or /O2 passed to the compiler (for GCC and MSVC++, not sure about Clang).
    - pflanze 12y ago
      You can't count on it in the general case even with gcc (even when taking care to heed the restrictions like not passing pointers to data on the stack, and putting all functions into the same compilation unit). I did tests a couple years ago where it would compile up to about a handful of mutually recursive functions with TCO, then when you added one more, it would disable TCO. I guess because some algorithm will stop analyzing the call graph past a certain mark and then disallow TCO from being applied.
    - pjmlp 12y ago
      If it isn't on the standard, anything goes. There are much more compilers out there than those three.
  - actsasbuffoon 12y ago
    TCO is available in plenty of other languages as well. Scala, Clojure, Erlang, and Elixir support it out of the box. Ruby has a VM setting for it, and there was a proposal to add it to JavaScript. I'm sure there are plenty of others.
cheery 12y ago
It depends on what you call 'everyday imperative-style code'. Without defining that, every answer to your question is correct.
skriticos2 12y ago
Admittedly recursion is not done often, but in some cases it's very useful. For example, recently I created an application with a tree record structure where the user could delete a node and it needed to delete all sub-nodes. With recursion it's easy to tell: 'call yourself for all subnodes you have, then delete yourself'. This is something that's much more difficult to express with the usual for/while constructs. Example: https://github.com/skriticos/tac_workflow/blob/9890e66d60851bd36af244294d94e1418e7b410d/workflow.py#L45-L49 https://github.com/skriticos/tac_workflow/blob/9890e66d60851...
al2o3cr 12y ago
Recursion can be a good fit for anything that's using a naturally-recursive process: for instance, when processing files in a directory along with all the files in subdirectories. Stack limits may or may not be a concern, depending on the application. In the case of directories, if you've got them nested 10k+ deep you've got other problems.
axman6 12y ago
I've written some nice, very clear C code using recursion; a nice example was a simple copying garbage collector which has something like 2-3 words of overhead on the stack per recursive call (made use of some global variables to reduce the number of arguments passed between functions though). The actual moving code was only maybe 10 lines.

chrisbennet 12y ago

re.curse v. To curse again.

chrisbennet 12y ago
Really? Downvoted because you lack a sense of humor?
- axman6 12y ago
  People are downvoting because this is not reddit. Off topic discussion is far less welcome here (though tolerated if suitably interesting).
  - chrisbennet 12y ago
    Thank you.

PaulHoule 12y ago

Recursion isn't allowed for safety critical code in automotive or avionics applications http://spinroot.com/p10/rule1.html http://spinroot.com/p10/rule1.html

Retric 12y ago
The rational is vary reasonable. Basicly, all recursion can be replaced by a loop that does not risk blowing the stack or using extra memory. However, tail call optimization is basically the compiler doing that conversion for you which also removes the risks.
- liotier 12y ago
  > tail call optimization is basically the compiler doing that conversion for you which removes the risks. Then can one argue that loops vs. recursion is mostly a matter of style and loops just as good as recursion since the compiler will optimize them that way anyway ?
  - dspillett 12y ago
    Yes, but only in the cases where the tail recursion optimisation is applicable. Recursive constructs are can be not tail recursive (and usually are with new starter developers) and many languages ignore it anyway (meaning even code that can be unpacked from function calls into a loop are not so the stack is still used).
  - rubiquity 12y ago
    Yes, but humans mess up loops far more frequently than compilers do. If we follow your argument recursively, we would all end up writing assembly language again, wouldn't we? :)
    - coldtea 12y ago
      Is that meant as an argument against loops and pro recursion? Because humans also screw recursion all the time.

vanderZwan 12y ago

So I guess, if we look past the topic of recursion itself - that the moral of the story is that design by committee works if kept in check by a benevolent dictator? Perhaps it works both ways: that a benevolent dictator can be properly grounded by a committee.

agumonkey 12y ago

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.

ced 12y ago
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
- owyn 12y ago
  I would LOVE to see that lecture...

juliangamble 12y ago

There is a book called The Little Schemer (was The Little Lisper) - a book all about recursion. This is a quote from a review: Little Schemer is without a doubt one of the best books I have ever read on the subject of recursion, and what is interesting because they never really go into a formal definition of what recursion is, as most texts on computer science try to. Instead they show the reader time and time again what recursion is, while providing a great series of rules (commandments) on how to get the most out of recursion, particually in a tail-recursive language like Scheme. http://www.amazon.com/The-Little-Schemer-4th-Edition/product-reviews/0262560992/ref=cm_cr_dp_synop?ie=UTF8&showViewpoints=0&sortBy=bySubmissionDateDescending#RCZ626B7P2J1C http://www.amazon.com/The-Little-Schemer-4th-Edition/product... You can read more about The Little Lisper here: http://thelittlelisper.blogspot.com.au/2010/06/little-lisper-chapter-1-toys.html http://thelittlelisper.blogspot.com.au/2010/06/little-lisper... Or you can read about working through it in Clojure here: http://juliangamble.com/blog/2012/07/20/the-little-schemer-in-clojure-chapter-1/ http://juliangamble.com/blog/2012/07/20/the-little-schemer-i...

davexunit 12y ago
The Little Schemer is fantastic. I recently picked up The Seasoned Schemer as well, but haven't gotten a chance to really dive into yet. I'm looking forward to seeing how the authors tackle more advanced topics using their out of the ordinary teaching style. Now, go cons a cake onto your mouth!
- Jtsummers 12y ago
  They've also got a 3rd book in the series, The Reasoned Schemer [1]. I didn't finish working through it (life and work and other things), but it's pretty good as well. [1] http://mitpress.mit.edu/books/reasoned-schemer http://mitpress.mit.edu/books/reasoned-schemer
  - davexunit 12y ago
    I want to pick that one up once I've gotten most of the way through The Seasoned Schemer, or if I see it through the window of the MIT Press store and can't resist.

kps 12y ago

> Ritchie relaxed the definition-before-use rule by allowing > redundant declarations of procedure headings. At the > expense of a redundant advance declaration the programmer > can define mutually recursive procedures in C. Point of order: C didn't have a declaration-before-use rule until C99. C had ‘implicit int’; no redundant declarations necessary.

craigching 12y ago
I thought ANSI C had that roughly around 1990? I remember having to forward declare functions when I took C at University in around 1991 or so.

bguthrie 12y ago

This is a wonderful piece of computer science history, and is of interest less for its nominal topic (recursion) than for the insight it gives into an early slice of languages research. Well worth a full read.

bodyfour 12y ago

The article doesn't mention why people didn't want recursion to be a requirement. It was probably because the idea of using a call stack was still controversial. For instance, on a PDP-8 (released some years after ALGOL) the calling convention was that the return address was written to the word of memory before the called function. This was simple, but pretty much precludes recursive calls. These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL/RET instruction pair. Before that was provided in hardware, the compiler would have to do that itself. So if you decided to support recursion, you'd end up requiring a stack and adding a small cost to every function call. Once you decide to have a stack, allowing recursion is a freebee so of course you'd include it.

Hemospectrum 12y ago
> The article doesn't mention why people didn't want recursion to be a requirement. It does, actually: > And this is what they wanted to remove because they wanted static allocation of procedure activation records. A stack frame is a dynamically allocated procedure activation record, but we no longer call them that because it's seen as absurd that they would be statically allocated.
- kibwen 12y ago
  I wouldn't say it's absurd, as it's legitimately very useful (though onerous) to be able to statically determine the amount of memory that will be used by a program. To this end, it is indeed true that tail-call elimination can remove the need for dynamically-allocated stack frames in the face of recursion. However, AFAIK, it is undecidable (given a Turing-complete language) to determine if a program contains only TCE-compatible recursion. In the face of that, you would have to forbid recursion entirely via a mechanism like the "declaration must precede use" rule mentioned in the article.
  - Chinjut 12y ago
    Whether a call is a tail-call is trivially decidable; it's an entirely syntactic condition (a call to f is a tail-call just in case it's of the form "return f(...);"). It's true that it's not possible to make a Turing-complete language for which it's possible to statically determine the amount of memory arbitrary programs on arbitrary inputs will use. But typically a language has other means of supporting dynamic memory allocation than simply via frame allocation for functions; e.g., via built-in operations to manipulate lists of arbitrary length. So, if you wanted to only allow recursion via tail-calls, you easily could, and if you wanted to furthermore go ahead and prevent all dynamic memory allocation, you could as well, but you would necessarily be giving up Turing-completeness.

auggierose 12y ago

I didn't know that F.L. Bauer was against recursion :-) In 1996 I participated in a summer school where he attended the talks we gave (mine was about Petri nets). Funny to see him mentioned here as a figure of history.

deleted 12y ago

[deleted]

mcguire 12y ago

"For example, in [6] the lambda calculus is defined in 86 lines distributed over ten definitions. It seems clear in this compact definition that lambda calculus does not allow recursive function definitions. Yet already by 1935 at least two versions had been discovered of the Y combinator, an expression of the lambda calculus. And this combinator makes recursive function definitions possible in lambda calculus." My understanding was that without recursion the lambda calculus is not Turing-complete. Is that correct? It should also be noted that recursion is a close relative of induction, an indispensable tool that is not without its own problematic history.

groovy2shoes 12y ago
That is correct, but recursion in the lambda calculus is emergent from the rules, not a rule in itself.
andreasvc 12y ago
Mathematical induction is not controversial, it is a formally correct method of proof. You may be thinking of the unrelated concept of empirical induction: generalizing from finite data (black & white swans etc).

lars 12y ago

This has some solid political advice courtesy of Peter Naur: If you want to get a committee to do what you want, show up with most of the work already done. That work became the starting point for all the future negotiations. And his influence on Algol-60 spec was a strong contributor to him receiving a Turing award years later.

deleted 12y ago
[deleted]

michaelfeathers 12y ago

The most interesting part of this story is considering what it would've been like if they decided to forbid recursion. Protecting the call stack from it would've been incredible overhead back then - either that or they would've had to enforce strict dependency ordered compilation and even then.. I imagine John McCarthy and the others who wanted recursion just sitting back and smiling, recognizing that that there was no need to press - it was just a matter of time.

abecedarius 12y ago
The boring way would anticipate C with "the behavior in that case is undefined"; it sounds like the less-formal attempt was like that. Cynically I'd expect such an outcome from a committee design, so Algol really was something special.

mark-r 12y ago

It may seem trivial now, but when this was being considered stacks were not a built-in CPU feature. In fact I wonder what was the first architecture that included one? The machine I learned assembler on would rewrite the instruction at the start of a function with a jump instruction to return to the caller. You returned from the function by jumping back to its beginning. Recursion wasn't an option!

deanmen 12y ago
This convention is even used in Knuth's MIX: http://www.jklp.org/profession/books/mix/c06.html http://www.jklp.org/profession/books/mix/c06.html
acqq 12y ago
To get even better idea, the memory used at that time didn't even have to have 8-bit bytes: http://www.computermuseum.li/Testpage/IBM-1401.htm http://www.computermuseum.li/Testpage/IBM-1401.htm "It came with 4,096 characters of memory [6-bit (plus 1 parity bit] CORE memory, constructed from little donut shaped metal rings strung on a wire mesh." The core memory is explained in the same book which deanmen linked (thanks deanmen!) http://www.jklp.org/profession/books/mix/c01.html http://www.jklp.org/profession/books/mix/c01.html

capkutay 12y ago

"Oh whoops, I accidentally called this function inside of its self! Silly syntax error....but it looks like I traversed a binary tree..."

DonHopkins 12y ago

Peter Naur is actually The Unterminator: a robot from the future, in which machines running non-recursive programming languages ruled the world. SkyNet had hit the wall of complexity because it consisted of so much legacy code written in non-recursive FORTRAN. Its only means of recursion was to build a robot and send it back into the past to change the course of history, and introduce recursion into Algol, against the wishes of the wiser committee members who suspiciously and correctly viewed recursion as a means by which computers could take over the world.