Most recursion is about as bad as goto coding methodologies.
Personally, I think it should be avoided in modern compiled languages too.
Haskell is fun to play around on, but it is horrific to consider using in a stable production environment. =)
Personally, I think it should be avoided in modern compiled languages too.
Haskell is fun to play around on, but it is horrific to consider using in a stable production environment. =)
[1] https://web.archive.org/web/20091206042608/http://projectfor...
There are shorter ways to admit you already sold your soul. lol =)
Your threads, co-routines, interrupt handlers, error handlers, all have to be careful not to stomp on someone else’s use of the same function, even if they’re not directly using a function recursively.
On the other hand, I almost never use naked recursion in Haskell. It typically do recursion indirectly through more familiar combinators such as for loops.
def process_that_tree(my_tree):
def _handle(node):
# do the things
for child in node.children:
_handle(child)
_handle(my_tree.root)
Obviously for the filesystem these kinds of abstractions exist already in shutil/pathlib/glob, but it still can have a place for dealing with other kinds of hierarchies, like a package dependency tree or the like.
Do you never work with tree data structures?
I can't think of a non-trivial program I've written in the past two decades that didn't have some recursive tree traversal in it.
At some point you will crash because the runtime won't be able to allocate any more stack. And you can't preflight it because if you could preflight it you wouldn't be doing recursion.
Recursion is a nice toy, but in real life it's a ticking time bomb.
If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8.
This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.
I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day.
Recursion is fine.
In general it is naive, often dangerous, and an inefficient space/time trade-off.
I have been writing software for several decades... does that make one less insightful or more biased?
https://youtu.be/pmu5sRIizdw?feature=shared&t=31
=)
There may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine.
We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't.
Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.
Parsers are far from immune to these issues.
I think we will have to "agree to disagree" here... =)
with open('lulz.json') as ayy_lmao:
oops = json.load(ayy_lmao)
EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it.
EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting.
[1] EDIT3: on my machine in ipython right now it's 1485:
import json
def nest(d):
return '{"k":' + str(d) + '}'
def make_mess(n):
v = 1
for _ in range(n):
v = nest(v)
return v
json.loads(make_mess(1485)) # boomAnd yeah, recursion is avoided in some shops for good reasons.
You'll want to cap the maximum allowed nesting depth. Even if not using recursion, you probably don't want untrusted input to be able to make your stack data structure allocate arbitrary amounts of memory.
If you do put a nesting limit in, you can do that equally well using an actual stack or recursion. (For example, I believe v8 still uses recursive descent for parsing JSON and JavaScript. It detects and handles stack overflows to ensure that untrusted input can't blow the stack and crash. I'm not sure if it's using a hardcoded nesting limit or actually trapping the stack/heap collision somehow.)
Shouldn't you stick to a depth-first branch reply limit until moving to the next fork.
I want to respect your beliefs. =)
I've run into similar issues with recursive code in java. The story gets better in C or rust, but there wre still sharp edges. I guess there are sharp edges everywhere though...
def isRecursionOk(problem)
for (subProblem in (breakDownIntoSubProblems(problem))
if ! isRecursionOk(subProblem) return false
return trueMakes more sense to do it as breadth-first with only one return value:
from collections import deque
def isRecursionOk(problem):
q = deque(problem)
while q:
problem = q.popleft()
q.append(list(breakDownIntoSubProblems(problem)))
return trueThere are safer hobbies available like snake juggling =)
Of course you can, if you wanted to, just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue.
Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.
So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context.
Best of luck, =)
Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order:
- reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken.
- space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others.
- time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker.
> Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.
I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution.
EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.
My process for deciding when to use iteration or recursion is simple: if each step needs to keep context then use recursion, otherwise use iteration (unless recursion with TCO is the native idiom of course).
I've never had an issue that wasn't an obvious bug that iteration would have somehow solved. If any bug that terminated a thread was fatal to the whole process then I suggest the thread termination handler should handle this more gracefully.
Increased space usage is a non-issue IMO. Translating a stack frame to a data structure you manage as an explicit stack requires the same space within a small constant factor.
And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
Quite likely :)
> And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
This is a very good point.
Alright, you've convinced me to start playing with recursion again. Just not in java or python.
An easy way to do it is to just pass a separate "depth" integer parameter into the recursive function. It then passes that +1 when it makes a recursive call. At the top of the function, if the depth is above your chosen limit, you bail out in some way instead of continuing to recurse.
> you detect that situation and make it work.
If you really do need to "make it work" for arbitrarily-deeply nested inputs, then you are actually better off using a heap-allocated stack instead of recursion.
But in most cases, a recursive implementation will only exceed the stack if the input is malicious or pathological and you can just fail in that case.
I didn't actually say that, but even supposing I meant that, walking a 3D mesh in a way that requires you to keep stack context sounds like a pretty unlikely/niche scenario, so it seems even that stronger statement is true.
It's fairly intuitive to walk a mesh recursively by following adjacent edges and you have to keep track of where you've been which means storing a lot of data somewhere. Maybe there are better algorithms but sometimes you just reach for what's most obvious. I suppose there are many analogous applications of traversing a graph structure.
On the other hand, recursion extremely expensive in some languages and Python has a notorious limit that forces library writers to roll their own stack. So despite the above, I'm actually in the anti-recursion camp.
But it does you no credit to dismiss ‘web devs’ as more likely to be doing that kind of work. You know the web is full of hierarchies, right? Domain names, the DOM, JSON structures, file directories? And ‘web devs’ build complicated sites with navigation hierarchies and taxonomies and comment threads and team based permissions and complex data visualizations - because web devs build applications that model real world businesses and data all the time, and those things are complex and hierarchical and fractal.
Web devs have plenty of uses for recursion. Don’t be dismissive.
All commercial projects eventually become "work" when they are no longer fun, and you wouldn't show up unless paid.
You also can realize your NDA does not expire on some IP you wrote 15 years ago. lol =)
It seems like you're just trying to smooth over a relatively inoffensive point. I don't think most web developers would disagree with GP. You're the one being rude and dismissive of the person you're replying to, frankly.
Yes, you can use std::vector or array or similar as a stack, without using recursion (which has some easily reachable depth limit that is much smaller than what your full RAM memory allows, especially in e.g. JS)
Of course ideally programming languages would figure out a way to not have this reachable limit and allow as much recursion as your RAM allows... We're still in the ancient world when it comes to this, it seems
You are not lazy enough to be a good programmer yet. ;-)
Have to think "minimum effort" here... ;-)
That is efficient for most Java programmers. =)
Recursion for iteration is just more complicated iteration. I've never seen a good argument for it in modern programming, it just ends up being the classic backwards rationalization of something people want to believe.
Recursion for traversing a tree is just using the call stack as a stack data structure.
Any balanced tree is never going to exceed 64 levels deep (really 48 on a 48 bit memory addressing cpu) and that could easily be put in a static array that gets used as a stack without recursing. This is easier to limit and debug.
It's just as easy to limit recursion depth, if you need to, just pass along a counter and check it. I haven't found that hand-rolling a second stack, instead of using the program stack, is easier to debug, the opposite if anything, but your mileage may vary on that one.
Saving stack memory isn't the point (even though a static array definitely does, because instead of multiple pointers and variables on the stack it only would have to store the node index of a tree).
The point is that you can see the whole stack and all the data that you're using at one time in a debugger instead of trying switch through call stacks to find data.
Recursion means defining something in terms of itself, so no, using a stack isn't recursion. The call stack of lots of different function calls in a normal program isn't called recursion either.
the idea of having the problem solved by way of breaking it down into smaller problems.
That's not recursion, that's organization, modularity and all sorts of other descriptions. Where did you get these ideas?
https://en.wikipedia.org/wiki/Recursion
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself
Seems very inefficient for the risks it brings.
I think we all agree this is still very interesting to consider. =)
How can you differentiate between them? How do you account for these two things being isomorphic? Any algorithm that can be defined by calling itself can also be expressed by way of an explicit stack, just as any algorithm defined iteratively can be implemented via recursion (usually tail recursion). Using an explicit stack and the call stack is formally equivalent.
> That's not recursion, that's organization, modularity and all sorts of other descriptions. Where did you get these ideas?
From the same source as you. Namely the thing you quoted below:
>> Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself
I'd say that a "simpler or previous version of itself" would also be smaller since you're trying to get down to the base case.
Like if you're doing stuff with a binary tree, you usually have to consider the left and right subtrees, and whether they're empty or not, and if they're not empty, maybe do something like push a new entry onto a stack so that the left and right subtrees also get processed, and of course with them being empty being the base case.
The structure is inductively defined, which is why recursion is also the natural way to approach it. This of course being in contrast to dealing with codata and corecursion which deals with infinite structures.
One is a concept that means that something is defined in terms of itself, which why I linked you the definition. The other is a data structure where the first item in is the last item out. One is an abstract concept that isn't limited to computer, the other is an ordering.
Why do you think these two completely different things have anything to do with each other? You just keep saying they are the same for some reason. Repeating a claim is not evidence.
How do you account for these two things being isomorphic?
They aren't.
Any algorithm that can be defined by calling itself can also be expressed by way of an explicit stack, just as any algorithm defined iteratively can be implemented via recursion (usually tail recursion).
Being able to do something in a different way with a different tool doesn't make all ways and tools the same. I can hit a nail with a block of wood, that doesn't make the wood a hammer. You can use it as a hammer, but if you ask someone what it is they won't say it's a hammer.
Using an explicit stack and the call stack is formally equivalent.
My point above is that pragmatically they have a big difference, which is that it is easier to debug a static array stack because you can see the whole thing instead of having to walk through a call stack to figure out where the iteration went. It's also probably faster and simpler, but the point is the clarity and the ability to debug.
The structure is inductively defined
The structure is defined by the data. There is nothing "inductive" about it.
which is why recursion is also the natural way to approach it.
Again, what you are really seeing here is that the iteration of a tree matches the first in last out structure of a stack. Recursion just gives you a stack using the call stack, nothing more.
This of course being in contrast to dealing with codata and corecursion which deals with infinite structures.
This has nothing to do with what we are talking about.
Well first of all, both are abstract concepts. In particular, in computer science stacks are considered to be an abstract data type with a push and a pop operation, which both act on the "top" element of the stack.[0] And I'm sure that you already knew this.
The fun part here is, of course, that stacks are also a type that can be defined via structural induction. I.e. that you either have an empty stack, or a stack where the top has an item and then below is another stack which contains the rest of the elements of a stack. So something like this:
data Stack a = Empty | NonEmpty a (Stack a)
There's of course nothing magical about call stacks versus explicitly instantiated stacks. They're both particular manifestations of the abstract data type. Of course, you can easily argue that there's a difference since call stacks of course tend to get special support in hardware, but as per the original article, that was of course not always the case.
And this is not to mention that you can store "call frames" even with an explicit stack and then pop things off of the stack, until it's empty, in a loop. This is for example how usually recursive algorithms such as depth-first search are implemented in a more iterative manner. And this couldn't be recursion because... it's not written as a function calling itself? Do I understand this right? Because to me that feels like a quite arbitrary way to define what it means to "define in terms of itself".
> They aren't.
Well, I'm not going to ask for a full formal proof, but I would appreciate for some expansion of this point.
> Being able to do something in a different way with a different tool doesn't make all ways and tools the same. I can hit a nail with a block of wood, that doesn't make the wood a hammer. You can use it as a hammer, but if you ask someone what it is they won't say it's a hammer.
Well at least to me, it seems that the argument being put forward here is more that you can't use a block of wood to hammer a nail with, because a block of wood is not a hammer, and that you need to explicitly use a hammer to be able to hammer stuff.
> My point above is that pragmatically they have a big difference, which is that it is easier to debug a static array stack because you can see the whole thing instead of having to walk through a call stack to figure out where the iteration went. It's also probably faster and simpler, but the point is the clarity and the ability to debug.
Oh for sure, it's easier to inspect a stack if it's backed by an array. Of course one could also argue that this should be solvable by improving debugging tools, and making them better at showing call frames, but that's neither here nor there.
> The structure is defined by the data. There is nothing "inductive" about it.
Incorrect.[1] Trees are explicitly defined as inductive/recursive data types. And this isn't just the case for binary trees, but trees where you can have arbitrary amounts of children are defined like this, usually by invoking the concept of a "forest" which is a collection of trees.
> Again, what you are really seeing here is that the iteration of a tree matches the first in last out structure of a stack.
Well no, you could also go through a tree in a breadth-first traversal, in which case you wouldn't want a stack, but a queue, which is explicitly a FIFO. But yes, due to the structure of a tree, and it being a recursive data structure, of course you'd usually use recursion to iterate through it. And for that, you want a stack of some sort.
> Recursion just gives you a stack using the call stack, nothing more.
I don't disagree with this. If anything, it just serves my point. There's nothing special about using the call stack for this. Whether using the call stack or an explicit stack, you're still going through the tree in this case in way that takes advantage of its recursive nature of being defined as nodes with other trees as the nodes' children.
We could come up with an alternative name for this, if calling this general idea "recursion" feels odd, since you don't need to necessarily implement it as a function calling itself, but that doesn't fundamentally change the actual thing being done.
> This has nothing to do with what we are talking about.
Heh, fair enough. I just thought how it's interesting that both induction and corecursion deal with data by defining stuff from a base case and then expanding on that, but of course corecursion is based on coinduction, which of course goes the other way around, going from larger objects to smaller ones, which on the other hand is how recursion is usually thought of.
But yeah, not super relevant.
----
[0]: <https://en.wikipedia.org/wiki/Stack_(abstract_data_type)>
[1]: <https://www.cs.princeton.edu/courses/archive/fall21/cos326/l...>
No they aren't. A stack is a specific type of data structure. Recursion isn't even specific to computers.
in computer science stacks are considered to be an abstract data type
I think you meant data structure and they aren't both concepts.
Of course, another way to refer to this kind of a structurally induced data type is to call it recursive.
You are making a linked list. A node in a traditional linked list has data and a pointer to the next node. This is what you are making here. Just because you over complicate a stack by using a linked list, it doesn't mean a 'stack' and 'recursion' are the same thing.
Fundamentally this is functional programming silver bullet syndrome. These things really have nothing to do with recursion, haskell is just putting a square peg in a round hole by using recursion for iteration and linked lists.
It's all fun and games until you get past trivial examples. Then pretending complex iteration and data structures are best done with recursion aren't so fun anymore and you want to control what is actually happening.
One example is this rust quicksort being 40x faster than haskell
You could recurse using an explicit stack or use tiny function that will thread themselves as see fit.
In a way it's more encapsulating than languages preaching encapsulation.
that will thread themselves as see fit.*
What does this mean?
In a way it's more encapsulating than languages preaching encapsulation.
Recursion does this? Are you talking about not depending on a stack structure in this specific instance or something else?
> Are you talking about not depending on a stack structure in this specific instance or something else?
- using recursion involves functions as basic block of logic, that represent sub-parts of a domain
- often creates finite set of self dependent functions
- all you do is call and pass other functions, that will call each others
> In a way it's more encapsulating than languages preaching encapsulation.
If you consider `map` or `fold` these create opaque functional processes that operate very automatically. It's all inductive logic at work to me. On the other hand in OO you needed (until very recently) to create iterators and empty structure to modify step by step.
> Are you talking about not depending on a stack structure in this specific instance or something else?
PEG parsing where the monadic flavor replaces an externally managed stack
ps: maybe i'm still too high on lambda calc
That's what functions do.
often creates finite set of self dependent functions
This doesn't have anything to do with recursion.
all you do is call and pass other functions, that will call each others
You this doesn't have anything to do with recursion.
If you consider `map` or `fold` these create opaque functional processes that operate very automatically.
I think you mean, they iterate for you. They don't use recursion.
On the other hand in OO you needed (until very recently) to create iterators and empty structure to modify step by step.
I really don't understand all this. You know most iteration is done with a for loop right?
PEG parsing where the monadic flavor replaces an externally managed stack
This seems like you're trying to write a satire of someone soaked in haskell. Everyone is else is just writing for loops and moving on.
recursion is compressing the domain so small it eats itself, crafting a small set of function is mirroring this, kinda like grammars
> You this doesn't have anything to do with recursion.
> I think you mean, they iterate for you. They don't use recursion.
afaik map and fold were defined recursively
...
foldl f z (x:xs) = foldl f (f z x) xs
> I really don't understand all this. You know most iteration is done with a for loop right?
that was what i was pointing at, iterators are not encapsulated enough
> This seems like you're trying to write a satire of someone soaked in haskell. Everyone is else is just writing for loops and moving on.
I'd appreciate if you didn't make it personal. Also, you forgot ocaml, lisp, prolog.
I don't think this means anything. At best it's a completely abstract claim with nothing backing it up. It isn't "compressing a domain" to do iteration differently.
afaik map and fold were defined recursively
Fundamentally they are useful because the do the iteration for you. Internally it doesn't matter if the iteration is done in a roundabout way with recursion, they aren't about recursion and don't really have anything to do with them, just because some language decides to do iteration with recursion.
that was what i was pointing at, iterators are not encapsulated enough
You keep saying iterators, I keep saying iteration, but the only difference here is that the recursive version hides the accumulation in the arguments on the function. There isn't any more encapsulation, just a variable moved into the function argument. The brevity is from haskell's type deduction, not recursion.
Map doesn't do iteration.
It's not about Haskell.
https://www.geeksforgeeks.org/python-map-function/
The whole point of map is that it does the iteration for you and you pass it a function. Iteration is literally the reason it exists.
Map doesn't simply iterate (that would be forEach), it creates another piece of information containing f(a) for all a in the input sequence.
What would iterating over a tree yields ? what would mapping over a tree yields ? how do you define the latter ?
Says who? You didn't back this claim up with anything.
Map doesn't simply iterate
No one has ever said it 'only' iterates, you hallucinated this claim. The whole point that I've made is that just because a language like haskell uses recursion for iteration, it doesn't mean iteration and recursion are the same thing or that things that iterate have anything to do with recursion.
Why would I need to back that up ?
> No one has ever said it 'only' iterates, you hallucinated this claim. The whole point that I've made is that just because a language like haskell uses recursion for iteration, it doesn't mean iteration and recursion are the same thing or that things that iterate have anything to do with recursion.
Why the mention of haskell all the time ? I'm not even talking about statically typed languages here.
The original conversation was about the intellectual benefits of recursion, not iteration == recursion. Recursion is a way to think about problems that I find more general, precise, creative and economical I tried to convey why, I'm not the most precise but this is getting nowhere. Feel free to enjoy your life.
Why do you need to back up the things you say? Because if someone believes anything without an explanation then they don't know what's true.
Why the mention of haskell all the time ?
Because you wrote haskell -> foldl f z (x:xs) = foldl f (f z x) xs
The original conversation was about the intellectual benefits of recursion
No, you made very abstract and bizarre claims like recursion is compressing the domain so small it eats itself, it's creating self sustaining computing blocks, and use tiny function that will thread themselves as see fit.
Statements like this that aren't even really coherent sentences, let alone explainable, are the types of things that happen when no one asks anyone to back up what they say. Evangelism starts to bleed into religion and anyone questioning the grandiose hyperbole is dismissed as an adversary.
I just copy pasted the first line of code in wikipedia, the definition is the same in ocaml, and in spirit scheme (list pattern matching syntax aside).
You're forcing your views on me, thinking I'm defending a Haskell cult which I'm not. Most of this came before Haskell was a language name idea. Probably even back to the late 60s.
And yes inductive reasoning is about compressing the domain in a finite set of disjoint cases that "eat itself" because you can reuse other parts of that domain in substructures. Wrapping all required information as function argument makes them self sustainable / encapsulated because nothing leaks out. It's not that much of a bizarre claim.
I'm just asking for something and you haven't given anything but big claims of the benefits of recursion without any explanations or example comparisons.
And yes inductive reasoning is about compressing the domain in a finite set of disjoint cases that "eat itself" because you can reuse other parts of that domain in substructures. Wrapping all required information as function argument makes them self sustainable / encapsulated because nothing leaks out.
This is still a grandiose claim without any explanation of what it is supposed to mean, let alone any explanation of why it is true, especially in comparison to other languages. Every language has functions.