4 ms·

so consuming stack frames is no reason not to use a recursive function. Saving stack memory isn't the point (even though a static array definitely does, becaus

so consuming stack frames is no reason not to use a recursive function. 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.

sham1 3y ago
Well, it's still recursion whether you're using the call stack or are using an explicit stack structure. You're still breaking the problem down into smaller subproblems inductively. I feel that people focus on the wrong things when talking about recursion, focusing on the aspect of having a function calling itself instead of the idea of having the problem solved by way of breaking it down into smaller problems.
- CyberDildonics 3y ago
  it's still recursion whether you're using the call stack or are using an explicit stack structure 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 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
  - Joel_Mckay 3y ago
    Except on most modern large CPUs on each recursive call the entire processor register state including program counter offset etc. are pushed onto the stack. Seems very inefficient for the risks it brings. I think we all agree this is still very interesting to consider. =)
  - sham1 3y ago
    > Recursion means defining something in terms of itself, so no, using a stack isn't recursion. 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.
    - CyberDildonics 3y ago
      How can you differentiate between them? 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.

sham1 3y ago

Well, it's still recursion whether you're using the call stack or are using an explicit stack structure. You're still breaking the problem down into smaller subproblems inductively. I feel that people focus on the wrong things when talking about recursion, focusing on the aspect of having a function calling itself instead of the idea of having the problem solved by way of breaking it down into smaller problems.

CyberDildonics 3y ago
it's still recursion whether you're using the call stack or are using an explicit stack structure 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 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
- Joel_Mckay 3y ago
  Except on most modern large CPUs on each recursive call the entire processor register state including program counter offset etc. are pushed onto the stack. Seems very inefficient for the risks it brings. I think we all agree this is still very interesting to consider. =)
- sham1 3y ago
  > Recursion means defining something in terms of itself, so no, using a stack isn't recursion. 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.
  - CyberDildonics 3y ago
    How can you differentiate between them? 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.