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.
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.