4 ms·

I agree. People love making things clever instead of making things done. Recursion for iteration is just more complicated iteration. I've never seen a good arg

I agree. People love making things clever instead of making things done. 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.

samatman 3y ago
The same argument suggests that a recursive stack traversal will never consume more than 64 stack frames, so consuming stack frames is no reason not to use a recursive function. 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.
- CyberDildonics 3y ago
  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.
agumonkey 3y ago
To my poor eyes it's creating self sustaining computing blocks. 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.
- CyberDildonics 3y ago
  Are you saying recursion creates "self sustaining computing blocks" ? What does that mean and how does it do it? 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?
  - agumonkey 3y ago
    I'm trying to make my ideas clearer but I'm not sure it will be :) > 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
    - CyberDildonics 3y ago
      using recursion involves functions as basic block of logic, that represent sub-parts of a domain 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.

samatman 3y ago

The same argument suggests that a recursive stack traversal will never consume more than 64 stack frames, so consuming stack frames is no reason not to use a recursive function. 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.

CyberDildonics 3y ago
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.

agumonkey 3y ago

To my poor eyes it's creating self sustaining computing blocks. 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.

CyberDildonics 3y ago
Are you saying recursion creates "self sustaining computing blocks" ? What does that mean and how does it do it? 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?
- agumonkey 3y ago
  I'm trying to make my ideas clearer but I'm not sure it will be :) > 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
  - CyberDildonics 3y ago
    using recursion involves functions as basic block of logic, that represent sub-parts of a domain 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.