• jjagaimo@lemmy.ca
    link
    fedilink
    English
    arrow-up
    18
    ·
    1 year ago

    It depends on if the problem is recursive or iterative, and how much it needs to be optimized.

    For example, you may use a for loop for a simple find and replace scheme for characters in a string, where you check each character one by one until you find one which matches the target, and then substitute that.

    There are certainly recursive ways to do string replacement in strings which might be faster than an iterative search depending on implementation, but that’s more optimization than I might need 99.9999% of the time

    A recursive problem that’s difficult to solve iteratively is browsing all the files in a folder and it’s subfolders. Each folder may have several subfolders, which you then need to search, but then each of those folders can have subfolders. This problem can be solved fairly easily recursively but not as easily iteratively.

    That’s not to say it can’t be solved that way, but the implementation may be easier to write

    Recursive code, however, is more frequently prone to bugs which causes infinite recursion leading to crashes, as it is not a tool which is often used and requires several more fences to prevent issues. For example, in the folder example, if one were to encounter a shortcut to another folder and implement code to follow that shortcut as if it were a directory as well, then placing a shortcut to a folder within itself might cause the code to recurse infinitely without having a maximum recursion depth and or checking for previously seen folders.

    • atheken@programming.dev
      link
      fedilink
      arrow-up
      4
      ·
      1 year ago

      I generally find that writing code that requires a lot of “accounting” is very prone to mistakes that are easier to avoid with recursion. What I mean by this is stuff where you’re tracking multiple counters and sets on each iteration. It’s very easy to produce off by one errors in these types of algos.

      Recursion, once you get the hang of it, can make certain kinds of problems “trivial,” and with tail-call recursion being implemented in many languages, the related memory costs have also been somewhat mitigated.

      Loops are simpler for beginners to understand, but I don’t think recursion is all that hard to learn with a bit of practice, and can really clean up some otherwise very complicated code.

      My general opinion is that we are all beginners for a short part of our journey, but our aim shouldn’t be to make everything simple enough that beginners never need to advance their skills. We spend most of our careers as journeymen, and that’s the level of understanding we should be aiming for/expecting for most code. Recursion in that context is absolutely ok from a “readability/complexity” perspective.

    • Nommer@sh.itjust.works
      link
      fedilink
      arrow-up
      4
      ·
      1 year ago

      Could your folder tree problem also be solved with a whole loop instead? I’m very new but it seems like recursion is harder but possibly more optimized approach to loops or am I incorrect here?

      • mercator_rejection@programming.dev
        link
        fedilink
        arrow-up
        8
        ·
        1 year ago

        Any recursive algorithm can be made iterative and vise versa. It really depends on the algorithm if the function calls are a major factor in performance.

      • Faresh@lemmy.ml
        link
        fedilink
        English
        arrow-up
        5
        arrow-down
        1
        ·
        1 year ago

        Recursion is never more efficient than the best equivalent iterative solution. Recursion however allows you to solve some problems very easily and very neatly.

      • jjagaimo@lemmy.ca
        link
        fedilink
        English
        arrow-up
        4
        ·
        edit-2
        1 year ago

        I’m exaggerating a bit there. This problem is fairly easy to implement iteratively (e.g. keep a list of unbrowsed folders and keep adding to it), but that is not the case for all problems. Some will be easier to solve in one way, though fundamentally solvable either way

      • coloredgrayscale@programming.dev
        link
        fedilink
        arrow-up
        2
        ·
        1 year ago

        A naive iterative implementation would be by adding and removing the folders/files from a list.

        If tail call optimization works on the (recursive) example then that’s (kinda) the compiler turning a recursive function into a loop.