5
sjwsjwsjw
174d

does recursion have any practical use outside of being a cute/elegant solution under constraints where stack overflow isn't a concern due to small input size, and leetcode?

im having trouble thinking of anywhere you could justify using recursion in industry outside of leetcoding people

i assume the iterative approach would be preferred in scenarios where scaling matters

Comments
  • 5
    Recursion is fundamental to truly understanding functional programming. It's not that recursion is useful like a shop class that teaches you how to make X or Y, recursion is useful as a philosophy class that is useful in changing the way your approach and think about things in the first place.
  • 4
    Recursion is the natural replacement for all loops when you think like a mathematician. You can implement a lot of algorithms quite beautifully using recursion - and in functional languages featuring tail call optimization, recursion can be as fast as a loop (because the compiler turns it into one).

    At the end it is a question of paradigm. Every loop or recursion can be turned into a recursion or loop (sometimes with help of an extra state stack) and tail call recursion actually is a disguised loop (or the other way round, depends on where you come from).

    And there are languages wich are based on strict immutability and single-assignment like Erlang (the modern syntax version is called Elixir). You can't reasonable use loops there. But recursive composition still works fine.
  • 2
    You're completely right. Recursion has no practical use outside of toy scenarios and weird languages that require its use. The iterative approach is pretty much always better.

    > when you think like a mathematician

    Yea, mathematicians have literally had thousands of years to figure out that single character variable names are bad practice and yet they somehow haven't figured that out yet. No programmer should be thinking like a mathematician, they should be thinking like programmers; if anything mathematicians are the ones that should change their ways and start thinking like programmers.
  • 0
    Recursion is not useful on its own.
    it can stackoverflow on certain inputs. It can have issues with thread safety (pointer passing), and can be very inefficient.
    When used correctly - memoization, input size limits, and thread safety taken into account, it can be useful. But iteration is almost always better to solve the limitation factors.
  • 2
    Recursion is pretty much the only feasible way for any scenario where you don't just loop, but have to store state for each level. Doing that in an iterative way would imply maintining a parallel stack manually instead of using the one that the compiler provides for free.

    Games like chess or checkers for example. If I play this move (modifiy board state), then my opponent could do this (modify board state), then I can do this (modify board state)... or, no, I better could do this (undo board modification, restore from the current depth level, modify board again with alternative move).

    These cases aside, I don't get the current fad of hating loops. Oohhh, they might loop too little or too much. Yeah no shit, that's what happens if the loop termination condition is wrong, and that also happens with recursion.

    But IMMUTABILITY! Hogwash, because copy-with-modification is just mutation in disguise.
  • 4
    @NotJeckel Then again, meaningful naming requires the variables to even have meaning.

    Math doesn't care whether your 'x' is the amount of fuel in your tank or the amount of cumshots in a pr0n clip. It just examines the relation between x and f(x), and it doesn't care whether f is the remaining mileage or the amount of dollars paid.
  • 2
    How do you parse a tree without recursion? I suppose I should learn how to without recursion at some point.
  • 1
    Iterating trees which is actually quite common
  • 1
    @Fast-Nop: In Erlang, they actually take immutability seriously. It isn't just copy on write. If you want to modify a structure, you have to reconstruct it from the ground up like you want it. You obviously can reuse as much parts of the original structure as you like though - they are immutable so they can't change after the fact.

    Erlang is a single-assignment, immutable data, functional language designed for massively parallel message-passing-orineted multicomputing with transparent inter-process and inter-system capabilities built into the language.

    Ericsson made it in 1986 for its large-scale telecom applications and, while it definitely is one of that niche languages, it has some pretty impressive properties even for today:

    https://en.wikipedia.org/wiki/...

    I would totally use it for massively parallel but individually lightweight workloads today. Although i probably would use the Elixir version which modernizes the syntax a bit.
  • 0
    @Oktokolo Reusing the orginal structure and modifying the desired parts into a new variable is pretty much what I described. Yes, the individual variables are immutable, but you still have to track the state because that's what the program is about in the first place.

    Another reason why immutability is a mixed bag: yes, you get easy concurrency, but the price is that you now have to deal with stale data. That's not an issue if they are independent anyway, but then concurrency is also easy without immutability.

    And that's only for code that does computation - as soon as it's instead about behaviour, all of that goes out of the window anyway.
  • 0
    @Fast-Nop Sure, but even if there is meaning, the mathematician would still use the single character name. This is shown in your own example, since "f" means "function", right? So even when there is meaning, it's still single characters all the way down.
  • 0
    @NotJeckel yes, but that's common and hardly avoidable because what do you do with f(g(x))?

    Also, it's not just math, but also physics. t, m, v etc., that's a common convention. It also means that you don't need to translate that because try reading physics formulas written in German long form when you don't speak German.
  • 1
    I work for an ecommerce company. Guess how categories (of products) are stored?
    A tree.
    How do we parse a tree?
    DFS/BFS (recursively)

    We often use dependency injection, or DI (for example Guice injector in Java).
    How does they maintain dependencies? A graph.
    How do you traverse a graph?
    Mostly recursion.

    I had to list directories and nested directories all the way down to actual files, in HDFS.
    What do I use? Recursion.

    I once had a library giving wrapped exceptions - sometimes 3 layers, sometimes 4, sometimes 2... How did I unwrapped them?
    Recursion.

    Recursion at times is a very elegant way to make the code readable.

    At the end of it, code readability is a very under appreciated trait. Afterall, everyone jumps ship at some point, or just moves to another project and a newbie might have to maintain the current project.
  • 1
    I did a search for how to do tree parsing without recursion in C++.

    I found this:

    https://geeksforgeeks.org/inorder-t...

    It uses a stack. I suppose this might be advantageous over recursion if the stack is stored on the heap. Which, my guess, it is with std::stack. This sidesteps the stack overflow issue with large datasets I guess.
  • 1
    @Fast-Nop: State is conserved by passing it on to the next iteration of oneself. Because of single assignment, Erlang obviously can't have loops - but it has tail call optimization...
  • 0
    @Fast-Nop That's some compelling reasoning, so I guess you use a lot of single character variable names in your code?
  • 1
    @NotJeckel Code isn't math. Code is there to implement some specific purpose. Not like math to examine general abstract relations between things.

    Also, of course I do name my loop variable "i" and not "index".
  • 0
    Recursion is important as a concept. Some problems are solved more readable and easily using recursion (for example graph or tree traversion as stated before). In other words thinking in terms of recursion can help you solve problems more intuitively. If need be you can always transform a recursion into a loop with stack, but directly coming up with the loop solution might be more complicated at first in some cases.
Add Comment