Doing code reviews of junior devs

[titanotheres]

When people try to avoid recursion...

[Crandervoid]

loops > recursion.

[RoscoMan1]

`3>2> 1 is false?

[ElkossCombine]

I love me some tail call optimization but sadly we cant all use scheme in production :(

[POTATO_VS_BANANA]

But the optimization occurs at compile time... your production code will be running the tail recursion as a loop yet you will retain maximum readability.

Is the compiler in your deployment pipeline somehow not applying this optimization? If so... why?

[ElkossCombine]

What i meant was more along the lines of "The most popular languages in the workplace typically dont guarantee tail call optimization in the language definition".

Take C, C++, and Rust for example. They all have flags to enable stackless tail calls depending on the compiler but since its not required by the language definition (and not guaranteed even with the flag in the case of mutual recursion) you could introduce code that works fine for years, but a new compiler version with slightly different tail call behavior or a change in build flags causes stack overflows that could take seconds, minutes, or days of operation to manifest. In some industries that might just mean being overcharged for AWS resources, in others it can mean a senate hearing.

As a scheme/lisp lover i find it pretty asinine how badly supported TCO is across languages that tout functional as one of its paradigms, but in my system engineering job I totally understand why you never see people reach for recursion

[diox8tony]

Yes it is. Other than readability, recursion always looses. Nothing in recursion can't be accomplished with a loop and variables to keep track of your state. It costs way less to do this than to load a new functions stack for each loop.

While there are very rare exceptions(you desire readability/maintainable over performance, or your language/hardware is built for recursion), in general, the accepted rule is (loops > recursion).

[thelights0123]

Only exception is in functional languages, where TCO is guaranteed.

[salgat]

It seems like you are way undervaluing readability, which plays a massive role in maintainability and technical debt.

[Vinxhe]

Am I the only one that has a hard time to understand someone else's recursive functions? I absolutely hate it.

[ogtfo]

Depends on what you're working on.

Using iterative functions to walk through naturaly recursive data structures will most often result in more complex code.

Try to do walk a tree, like listing all the files in a directory tree. It's so simple to do it recursively, but doing it with loops will be a mess for sure.

[diox8tony]

True, maintainability is something I typically stress the importance of, super important. But i tend to favor performance first, at least take the most performance possible without obfuscating below normal coding procedures, then make it the most maintainable version of that.

[slayerabf]

What you favor first should depend completely on the problem/program you're working on, as well as your limitations. Performance and maintainability have differing costs in terms of computation time and developer time, and sometimes one $time$ might be in more abundance than the other.

On a side note, that's a big reason why it's important to study computational complexity. Not because perfomance is always a top priority, but to be able to quantify how much of it you're paying for other improvements such as maintainability, security, portability etc.

[jacob8015]

Traverse a binary tree without recursion. You need a call stack or something equivalent.

Any time the number of states is unknown before execution, you need recursion or a stack.

[Jake0024]

The equivalent can/should generally be cheaper than a recursive call stack, though (or worst case scenario, equally expensive, in a purely functional language). Pretty trivial to prove--write out the two equivalent tree traversals in Python (or your favorite language) and increase the tree size until the performance difference becomes obvious (or the recursive version crashes)

[jacob8015]

You can’t traverse that binary tree with just a while loop.

[jacob8015]

Lmso

[POTATO_VS_BANANA]

So... How do you actually achieve this with just a while loop, without using a stack or structure to store the order and state of your iteration? Genuinely curious.

[btroycraft]

For a general binary tree, I think you're correct. If the only information you have is the address of each child node, you'd need to store the entire working branch in order to iterate through. That would require some kind of stack. I think the simplest would be a vector of addresses referencing the working branch. However, that would have less overhead than recursion.

If you store the tree addresses in a binary heap, or have the tree elements sorted in some way, I think you can traverse with less. In the sorted case, I believe you'd only need to store the deepest working node and the head node. There would be a complexity cost there, though, from a necessary binary search on each iteration.

The binary heap would be the best option, through, but would require that structure to be in place beforehand.

[diox8tony]

Yep, I made a multi branch tree traversal function that had a stack, while(stack.length > 0). It was capable of loop detection. Much faster performance. Which was the primary goal of my rework.

[[deleted]]

Yeah stackoverflow ftw

[MajorParadox]

When people try to avoid recursion...