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.
> 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.
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.
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.
> So, if you wanted to only allow recursion via tail-calls, you easily could
To be fair, we're talking about a language designed in 1959, where a compiler had to run in 4KB of memory or so. At that point you're barely optimizing anything, just doing the simplest transformation you can.
Doing tail-call elimination isn't quite as simple as just doing a "JMP" instead of a "CALL" since you also need to replace the currently in-use activation record. Consider the C fragment:
int f(int a, int b)
{
if (a > b)
return f(b, a);
// ...
}
Now imagine you're trying to compile this for an ancient register-less machine. We have to replace "a,b" in the activation record with "b,a" but if we just naively copy the values one by one we'll step on "a" before we read it and end up with "b,b".
These problems certainly aren't insurmountable, but if it takes a few hundred instructions you've already blown a lot of your budget on one little feature. You could see why a language designer in 1959 would want to leave it out.
I don't see the relationship between Turing-completness and dynamic memory allocation.
Even in a classic Turing machine I interpret the tape as a single pre-allocated array (of infinite size).
When talking about Turing-complete programming languages, a relaxed definition with finite-size memory is assumed, and to me it seems that it's just hair splitting whether program hits that limit via malloc() call or by advancing a pointer in an internal fixed-size array. Dynamic memory allocation is just a name for a bunch of bookkeeping done on a fixed-size memory.
In practice asm.js programs are not allowed to dynamically allocate any memory from the browser: a fixed-size array is created before the asm.js program starts. From the point of the VM programs are just shuffling bytes within a fixed-size array, and yet, we can run "Turing-complete" programs in asm.js.
A finite memory machine is a finite state machine. These are not Turing complete. The notion of Turing completeness becomes uninteresting if we can't even draw this distinction.
"dynamic memory allocation" may not have been the right term to use to denote moving beyond finite state machines, for an audience which wants to consider a Turing machine as having statically allocated infinite memory. But it makes sense if you think of a Turing machine's memory as only storing enough data for the portion of the tape which has already been accessed, and allocating new memory as new tape regions are needed.
It's true that the actual machine sitting on your desk only has a fixed finite memory. In that sense, without a peripheral unbounded store, it's not properly Turing complete.
It's also true that we often find it convenient to analyze it as Turing complete anyway, but this abstraction basically goes hand-in-hand with abstracting away its memory limitations. I don't see any point in pretending you can be Turing complete using only programs with a statically given memory bound (which amounts to a logarithmic bound on the number of states in a corresponding finite state machine); if we're going to pretend, let's pretend the memory is effectively infinite as well.
The problem with analyzing programs in the context of a fixed memory limit is that you would have to revisit all of the proofs whenever the fixed limit was increased. If you can prove something true for unlimited memory, it's also true for any limited amount of memory.
>>we often find it convenient to analyze it as Turing complete anyway
It's convenient, because the proofs will still be true even if memory sizes grow by 500x. Turing machines clearly don't have a real, material existence, similarly to real numbers (assuming that all actual numbers are finite). Real numbers can be considered as modeling integers that are arbitrarily large.
I'm not sure how to untangle it, but I think you've got your abstraction layers mixed up. Anyway, that infinite tape is critical to Turing completeness. So strictly speaking, a limited-memory computer isn't strictly Turing complete, just close enough as makes no difference, because in practice they can use as much memory as they want, via dynamic memory allocation. When you tell the program it can't use as much memory as it wants, by taking away dynamic allocation, then you're not only not Turing complete, you're not even close to the Turing machine model.
I don't think it's that absurd. For example, IIRC the allocation size for stacks inside the Linux kernel is usually 8192 bytes (on x86). Consequently, people avoid stuff like recursion in kernel mode. Today.
Yet activation records are still dynamically-allocated from those 8192 byte stacks - they have to be, because Linux runs on SMP machines and the same kernel function could be executing on multiple cores at once. (Also, for big pieces of kide lke the Linux kernel, it'd probably be more expensive not to dynamically allocate them.)
> 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.
Not really; most risc architectures still manage the stack via the compiler rather than instruction. About the closest you get is a jump-and-store-link-register instruction.
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.
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...
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.
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.
Be warned that, despite the name, the Reasoned Schemer is only tangentially about scheme; it focuses on miniKanren, a somewhere-in-the-Prolog-ballpark logic programming language created by one of Friedman's students, that is implemented as an extension to the Scheme language proper (among other languages, most notably as the clojure core.logic library).
Also Friedman and Byrd did show up to a few clojure talks and seemed, from the online videos, to be highly entertaining - I remember their using miniKanren to automatically generate scheme programs that evaluated to 6 being particularly fun.
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.
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!
"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!)
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.
Well, if the compiler will also report error for recursive calls not in tail position...
There are strategies to prove various things about recursive calls. See Ada/Spark's explanation for Rule 17.2 in [1].
I'm not familiar with Coq and Agda, but I believe they allow recursive calls if they can prove termination, though "termination" may be different than "using too much stack".
As a rule of thumb, they permit recursion where one parameter "obviously" is getting smaller each time, with a base case at 0 or the empty list or whatever.
You can annotate the program in ways to make the compiler see that a parameter is actually getting smaller.
Replacing recursion with a loop can easily use extra memory. The usual approach is to implement a stack using a local variable: each iteration pops the head and processes it; rather than recursing, we push a new item and let the next iteration process it for us.
If the algorithm is tail-recursive, this will use constant stack space and memory, just like tail-call optimisation. If the algorithm's not tail-recursive, it will use constant stack space but large (potentially exponential) amounts of memory.
There's no way around this. The only solution is to come up with a different algorithm (eg. using an accumulator).
You're usually better off with manual recursion, if you're concerned about running out of space, for the simple reason that it's far easier in practice to back out of an out-of-memory situation than from a stack overflow.
Optimal loops don't use more memory than recursion and generally significantly less. Though if you can find an counter example in a common programming language I would love to see it.
However, we are talking about the automotive and aerospace industry so recursion overhead is often a deal breaker even if there are no other issues.
> Basicly, all recursion can be replaced by a loop that does not risk blowing the stack or using extra memory.
This isn't true at all. You can replace all recursion with loops, sure, but you're going to have to simulate a stack (i.e. use extra memory) to convert complex recursive functions to loops.
I believe that there is a better reason to ban recursion - it may mask possible execution time of code. Loops are more explicit in that regard. If you are writing a real-time system, you care about those things a lot. Ban of dynamic memory also may be caused by requirement to be real-time.
> 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 ?
Not all recursive functions can be rewritten to be non-recursive. The Ackerman function is one such example. It's clearly tail recursive, but not only tail recursive so it must use some kind of stack or tree or something which isn;t linear like a loop. there's some explanation on the Computerphile youtube channel discussing it: https://www.youtube.com/watch?v=Mv9NEXX1VHc
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).
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? :)
I guess. But if I make the mistake of infinitely recursing I find out the next time I run my program. If I'm writing my own loops and make an off by one error it could go uncaught potentially forever.
One of my favorite PHP gotchas is to accidentally write a function that calls itself infinitely, and then have the interpreter die without a warning message.
If a program is only doing a simple calculation and it's still running an hour later, you should probably suspect an infinite loop and not wait for it to stop.
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.
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.
> 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.
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.
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.
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.
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.
> Stack limits are pretty large. It's a natural way to express many problems such as graphs (and their subsets trees).
Coincidentally, I had a stack overflow while working on some trees a few months ago, it ate all my ram within about 2 seconds. Although my stack was sizeable, my program was blind and unaware of the stack limit.
Other languages probably do this too, but some Scheme implementations don't have a stack limit, or no stack at all. So you can define certain functions (map being a notable one) using their natural recursion and not worry about exhausting the stack with large inputs.
That's because of TCO, not because of a stack limit or its absence. A non-tail-call version of map would still blow up when you run out of memory, whether the implementation uses a stack like C, or keeps the stack on the heap (as I understand some scheme implementations do, particularly for dealing with continuations).
Yes, of course you can exhaust the heap, but there are some tricks that can be done to make it not much of an issue. For instance, "Guile arranges to return the unused part of the stack to the operating system, but without causing the stack to shrink." [0]
So, thanks to that, we can define map the clear and easy way:
(define (map f l)
(if (pair? l)
(cons (f (car l))
(map f (cdr l)))
'()))
Further down in that document, and in your quoted portion, it's clear that this doesn't prevent stack growth to the limit of the system's memory. It only mitigates the issue. They double the size of the stack (by default) when they hit the current stack limit. When the GC happens they take the still unused portion of the stack memory and turn it back over to the OS by freeing it. If the recursion is still too large for the overall system memory it'll still hit a limit (system memory), they've just succeeded in delaying it for non-tail recursive functions.
That said, it is a nice way to reduce the chance or delay the occurrence of hitting the stack limit (whether it's on the heap or an explicit stack that's still what's happening).
Well yeah, if you can make a procedure less than O(n) in space by using tail recursion, you should. But in the case of map, you might as well use the stack, since you have to reverse the list in the tail recursive version anyway.
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?
Most C++ compilers perform TCO when convenient, but the C++ language doesn't guarantee that TCO will be done, so it's unwise to write code that depends on it. In practice, every compiler decides when to do TCO in its own way. Also, it's useful to be able to run code with optimization disabled. Also, it's easy to accidentally have a variable that needs a destructor call which makes TCO impossible. This is all in contrast to Scheme, which does give you a guarantee, and which makes it easy.
It's implementation-dependent; a particular compiler may do it, or may not. Scheme, OTOH, has it written in the spec--you WILL do tail call optimization, so programmers can count on it.
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.
Per ch4s3's comment on Clojure, Scala also does not have TCO, at least, last I checked. The JVM doesn't allow it. It has a specialized handling of functions that call themselves, which it can optimize, but A that calls B that calls A that etc is not (nor, in the more general case where any function that ends with a function is removed from the stack).
To add a finer point, Clojure doesn't have TCO per se because the JVM doesn't have tco. Recur optimizes the special case of "tail-recursive self-call and not the generalized tail call."[0] That is to say when the tail of A calls A, but not when A calls B which calls A.
That's not accurate. In fact, in the .NET 2.0 timeframe the opposite was the case (the 64-bit JIT would fail to honor the IL tail. prefix in many cases, though it would also make tail calls in other cases even when the prefix wasn't applied)[1]. But as of .NET 4.0, both platforms honor the tail. prefix except in a very limited set of circumstances[2] (e.g. calls from untrusted code to trusted code).
As far as I know, F# is the only reasonably popular .NET language to emit the tail. prefix, though[3].
The problem with TCO in C++ is destructors; unless you're using a very limited set of types, they all but guarantee you're going to have code to execute after returning from what would otherwise be a tail call.
TCO isn't really transparent to the programmer. Some recursive calls cannot be optimized, so the programmer has to know how to write recursive functions that can be.
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.
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.
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.
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?
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.
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.
> 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.
> 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.
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.
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.
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.
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.
"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.
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).
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.
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.