How recursion got into Algol 60: a comedy of errors
vanemden.wordpress.com
vanemden.wordpress.com
Then one day I got one to laugh at this byte-saving routine to do some multiplications:
X32: BSR X16
X16: BSR X8
X8: BSR X4
X4: BSR X2
X2: ADD A
RET
int x2(int x) { return x + x; }
int x4(int x) { return x2(x) + x2(x); }
int x8(int x) { return x4(x) + x4(x); }
int x16(int x) { return x8(x) + x8(x); }
int x32(int x) { return x16(x) + x16(x); }Maybe I don't understand what the word recursion means, but I thought that you'd have to call yourself directly or indirectly.
You could state it that the multiple by a power of two is the sum of the multiples of one order of magnitude base 2 lower.
By these definitions, all but the most trivial code is recursive.
// e is a power of two
int mult(x, e)
return e==1 ? x : mult(x, e/2) + mult(x, e/2)
endThe piece of code in question was to use the chip as a smart power controller. Worked pretty well, aside from the limited code space.
Here's a blog entry about the little project: http://www.dadhacker.com/blog/?p=1911
Apparently the original code did multiplies by 10s, so the leaf routine was a few more instructions.
First of all, that's the top 0.01%. Second of all, with that strategy, no you don't because the top 0.01% are going to walk out of interviews that ask dumb brain teasers. The best programmers are ones who can solve problems in the context of a team and codebase, with the help of the internet and iteration, not solve obscure but not-really-that-hard problems in 15 minutes.
Here is one of the more interesting applications, a function that converts a 16-bit word in a register to a string of 4 hex digits in only 24 bytes of code, and can also be called to convert bytes and nybbles (x86):
; output value of AX as four hex digits to ES:DI
write_hex_word:
xchg al, ah
call write_hex_byte
xchg al, ah
; output value of AL as two hex digits to ES:DI
write_hex_byte:
push ax
shr al, 4
call write_hex_nybble
pop ax
; output lower nybble of AL as hex digit to ES:DI
write_hex_nybble:
and al, 15
cmp al, 10
sbb al, 69h
das
stosb
retOf course, your cow-orkers might wish you hadn't, depending on the amount of restraint you can summon :-)
Lisp was used quite a lot even after Algol 60 was standardized; presumably that would have occurred at least as much if Algol 60 was standardized without support for recursion -- inevitably, actually, moreso if Algol 60 didn't support recursion.
Maybe, including recursion in Algol 60 didn't make recursion mainstream, it just stopped Lisp from being more mainstream and made Algol 60 and its descendants successful.
Really, its hard to know.
> Do not write recursive procedures. Do not use procedures recursively.
I've probably failed 90% of recursion "gotcha'" questions I've had during interviews. It's my uninformed opinion that recursion is uninteresting and unintuitive. This is why whenever I encounter it, I either ignore it or refactor it. I'm exaggerating, of course, but I really do hate it. There are some very interesting theoretical applications, however. The article briefly mentions Lambda Calculus (which I love) where I've always enjoyed playing with the divergent Omega combinator[1]:
Ω = (λx. x x) (λx. x x)
I'm may be entirely too stupid to appreciate the beautiful intricacies of recursive programming, but I do think that recursive programming can be susceptible to some unique bugs, such as exceeding stack/heap, that are very difficult to notice prima facia (more difficult than when the same is done via procedural code, at least).
[1] http://www.seas.upenn.edu/~cis500/cis500-f06/lectures/0925-2...
If you are just doing a simple search, maybe you don't need to keep that whole stack around. An iterative approach makes a lot of sense. If you are building a map of the tree and you're not even sure what scale to make it, you might want to reserve judgement about the supertree while you explore some sub trees so you might be glad that stack is there, and you might profit from thinking about that situation as recursion.
But the answer is: yes, a lot of things you do with trees make a lot of sense as simple procedures.
Other stuff, not so much. Consider the Fibonacci Sequence written recursively.
Isn't it the recursive version which is hard to explain? The n'th Fibonacci number is the sum of ...
The iterative solution is more like "start with 0 and 1, add them together to get a new number, then add that new number to the larger of the previous two numbers, and do that n times to get the nth Fibonacci number." That works just as well (or better, for computers and large n) as the recursive solution, but it's harder to explain, and it barely even hints at the most notable property of the sequence (that each number is the sum of the previous two numbers).
On the other hand, if I ask you to compute F_1000, it might appear very recursive. You know you could make F_1000 from F_999 and F_998. And you get F_999 from... But it wouldn't be impossible to answer this question with the same approach as the first. It's not a priori obvious that "I'll calculate F_0 ... F_999" is an efficient way to calculate F_1000, but of course that turns out to be much more efficient than the naive recursive solution.
But I think Fibonacci is not the best introduction because of this. I think something like GCD calculation would be a better problem to define recursively, because there really isn't an obvious "forwards" approach to oppose the "backwards" Euclidean algorithm.
"We have a sequential block of memory, and we want to store a sequence in it... hrm... I know, why don't we put the first element in this struct, and... I'll deal with the rest of the items elsewhere."
The main point I wanted to make was that you described linked lists as unintuitive specifically in the context of having access to sequential memory space. Linked lists are not, typically, used in that circumstance. They make much more sense, and I think become more intuitive, when you consider them in the context of non-sequential memory space.
Suddenly linked lists (doubly-linked) are looking pretty intuitive :)
Going down this route would probably result in a contiguous linked list. You can argue that this is still a linked list, but I still find it conceptually more obvious. For a billion elements, it's probably also a lot faster, too.
I'm all for code-reuse and componentization but common... recursion is programming 101!
I say this because I was originally a self-taught programmer, and I hated recursion too. Once I went to school for a CS degree, I learned how awesome it really was, and now I use it all the damn time.
A recursive function makes me do all these convoluted mental gymnastics when I'm just trying to figure out if Cinderella lived happily ever after or not.
It's like comparing Star Wars to Inception.
Ever?
Those are trees. Want to walk the UI to find an element? Trees. Want to manipulate the DOM? Trees.
Walk a file system?
Write a file system?
Trees and trees.
Furthermore, part of our indexing needed to follow imports to find the canonical name of a value, which is a problem very well suited to a recursive solution.
You may not have encountered these situations where recursion and trees have to be dealt with, but they absolutely exist.
I want to take my JSON, and store it in Dynamo.
I need to convert every object object embedded in my top object to a {"M" : {...}} structure, and every array/list to a {"L" : [...]} structure. So something like - {"a" : {"b" : [1]}} should become {"a" : {"M" : {"b" : {"L" : ["N" : "1"]}}}}.
The easiest way to write one function that can handle that in a generic way, no matter how complicated the data structure (barring hitting the stack limit), is recursion.
Rule 4 (recursion)
There shall be no direct or indirect use of recursive function calls.
[MISRA-C:2004 Rule 16.2; Power of Ten Rule 1]
The presence of statically verifiable loop bounds and the absence of recursion
prevent runaway code, and help to secure predictable performance for all
tasks. The absence of recursion also simplifies the task of deriving reliable
bounds on stack use. The two rules combined secure a strictly acyclic function
call graph and control-flow structure, which in turn enhances the capabilities
for static checking tools to catch a broad range of coding defects.
The coding rules defined here primarily target the development of mission
critical flight software written in the C programming language. This means
that the rules are focused on embedded software applications, which
generally operate under stricter resource constraints than, e.g., ground
software.
Only if you're sloppy about the inputs given to the recursive code.
Recursion isn't magical. It's deterministic, and is a function of some aspect of the input values. (Corollary: If it isn't, what the fuck are you doing?)
So NASA decided to solve the stack growth problem by limiting recursion. (Zero is a limit.) It could have done the other thing and limited inputs to recursive code, which would have required more careful code analysis (static and dynamic) to figure out what the limits should be. It's an understandable decision, but don't forget it's a trade-off, and one that could have gone another way.
I don't see the trade-off.
On one hand (if you allow recursion) you need "more careful code analysis".
On the other hand, if you don't allow it, you don't lose anything. You can write the algorithm in another way, and it would be just as fast and easier to reason about.
So what's the tradeoff? It's not like recursion brings some benefit that you lose if you disallow it.
This is where we differ, then: Some algorithms are more natural to write recursively. Sorting is a big example.
So any recursive algorithm using tail-calls would be better implemented as a for/while loop in embedded C contexts, the performance will be similar (should actually be better) and the memory is now constant instead of increasing.
Any recursive algorithms that can't use tail-calls, I'm honestly not thinking of common situations for these in an embedded context. Perhaps traversing certain data structures, but you can probably find a different data structure that will be sufficiently efficient and not require non-tail-calls. Even with sorting, if you have a small, fixed sized array you could implement a sorting network. If it's too large for that to be feasible in code, it's probably still a small enough array that insertion sort is efficient.
Recursion is the use of the built in stack data structure that the compiler manages for you.
If you are working your way through a data set with a well determined end state that you incrementally approach (be it the end of the list, or getting closer and closer to finding a value in a tree), and you have a need to backtrack, then recursion is a good way to solve the problem.
All recursive code can be rewritten to be non-recursive, you just keep track of your own stack data structure. This can be either not that much work, or a major pain, depending on the exact problem.
Bull, a function that is not primitive recursive cannot be rewritten to be non recursive.
Sources: https://en.wikipedia.org/wiki/Ackermann_function https://www.youtube.com/watch?v=i7sm9dzFtEI
It's my informed opinion that I personally often find unintuitive things to be uninteresting, because thinking about them is less rewarding.
I wouldn't take your lack of interest to be a sign of your lack of intelligence so much as a different distribution of intuition.
Haskell tutorials usually advise against explicit recursion, instead favouring combinations of map, filter etc. as the best choice, and failing that use foldl', foldr etc. With explicit recursion only being used if you really have a good reason.
I would find it very unintuitive that in a language I couldn't write a function that calls itself. That feels like an obvious thing (if we ignore all the implementation details).
When I first started programming I used recursion without knowing that it's called like that and I didn't expect it to be called in any special way at all.
I think even the most die-hard functional programming fans among us secretly know that this is a problem. It's why virtually every functional language implements tail call optimization, and why one of the earliest things that's taught to new students of functional programming is how to ensure that functions use tail recursion whenever possible. Sometimes we even go through some pretty impressive contortions because of this. Consider the case of continuation passing style.
The other is that a lot of people find recursion hard to understand. Others seem to naturally think in terms of recursion and think iteration is a headache. I'm not sure the two camps ever see eye to eye. It might be a brain wiring thing. Though perhaps practice rewires your brain - I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion.
I have spent a decade doing a mix of both. It really really really depends on the problem at hand what's easier to understand
Have to traverse a tree? Recursion.
Have to make a big thing out of small things? Recursion.
Have to add +1 to a bunch of numbers? Loop.
Here's one way to see why recursion is special. Look at it from the perspective of implementing the language.
If your language doesn't have recursion, you can treat every local variable in your program as if it were a static global variable. It's local in terms of name scope, but you can give it a fixed blob of memory that you pick at compile time.
This is exactly what early Fortran compilers did. foo()'s local variables go here, bar()s go here, etc. You can do away with the stack entirely, I believe.
So, without recursion, you can make your entire program only use statically allocated memory. You can be sure it will never, ever ever run out of memory.
I am curious to know if modern Fortran compilers still use static allocation for local variables when compiling in Fortran 77 mode. I'd guess the cache advantages of keeping parameters close together in memory compensates for the extra work of manipulating the stack, but who knows...
> And this is what they wanted to remove because they wanted static allocation of procedure activation records.
From what I can tell with a bit of digging, machines/compilers back then didn't even use return stacks for subroutines. Instead, they used self-modifying code (!).
To return from a subroutine call, you'd do something like this:
1. When compiling a subroutine, add a JUMP followed by an address to the end.
2. When you call a subroutine, modify the code to change that address to point back to the callee.
3. Jump to the subroutine.
4. When it's done running, it hits the last JUMP and jumps back to the caller.
With this, you don't need any concept of a call stack at all. But it obviously prohibits recursion since the later call would trash the earlier one's return address.
This meant you could support function calling without the need for a stack. However you can't directly support recursive (or co-recursive) functions. Nor could you ever do things like multithreading or shared libraries, although hose obviously weren't concerns at that time.
Today we think of the callstack as a fundamental part of the machine architecture, but at the time of algol-60 it was still a very contentious subject.
Oh _please_! The reality was the the common machines of the time didn't have todays fancy addressing modes. All memory addresses were global addresses. Thus, the _cost_ of making all memory access relative to a stack pointer was far from trivial. Of course, there was a work-around if you could forgo re-entrance (~ "thread-safety"): use static activation records, but saving it to the stack before the recursive call and restoring after. Still not exactly free.
PS: Using stack to simulate recursion doesn't count :).
Interestingly, writing a compiler. Since expressions nest, it's very hard to write a compiler for them without a recursive function for compiling an expression.
By the way, are recursive versions of sorting algorithms even shipped with standard libraries of popular languages?
In C++ it's hard to make the efficient and non-recursive. You can have a fixed-sized buffer (limits depth), or call malloc for a buffer (a single call to malloc can be more expensive than just doing the sort on the stack, and in general the C++ standard library tries hard to avoid mallocing).
So that would be how recursion "got into programming".
The comedy of errors is how recursion got into Algol, not into programming.
Is "Amsterdam plot" an idiom, or simply a colorful expression that occurred to Bauer? I haven't seen this expression before, but TFA repeats it several times in stylized fashion so I thought maybe I was missing the intended meaning?
However at the same time, this same process is used for evil quite often; as the US Congress clearly provides many examples.
The story evoked a personal element, going back to when I was first learning programming in the 80's. Early on one of the serious hurdles I encountered was recursion. (Another was pointers and indirection.) After struggling to wrap my brain around the thing that kept calling itself, I ran across a book, "Thinking Recursively" by Eric S. Roberts, 1986, which was enormously helpful.
I consider the book a classic. And it must be since it's still in print! I'd highly recommend it for anyone who finds recursion unintuitive. Way back then it wasn't intuitive to me either, but with the book as a guide in time it became as natural as breathing air.
Similar to the situation with things like CoffeeScript vs. ES6 etc.
What I think we need is a standard so flexible and meta that systems can evolve without waiting for society or standards to catch up. Which we have in Turing-complete languages.
But we should standardize somehow on a very meta level.
This is why we must demand macro systems in the languages we use. Building new languages is part of the programming process. Everyone should be able to do it, not just standards committees.
Offhand years ago I used a dialect of C that had no recursion so I can see both sides of this argument. On the one hand, there is a pain point when you don't have access to recursion. On the other, boy can a compiler that eschews recursion produce small and fast code. (Because without recursion the call graph is acyclic)
quicksort [] = []
quicksort (x:rest) = quicksort [y | y <- rest, y <= x] ++ [x] ++ quicksort [y | y <- rest, y > x]Are you really implying that if recursion was turned off in a modern compiler it could create better code?
Just saying, you add a feature to a language, you will pay something for it.
I swear we still have not learned from our mistakes; Although now its platform-independent with the platforms being mobile, desktop, and web.