this post was submitted on 22 Dec 2023
31 points (91.9% liked)
Programming
17313 readers
183 users here now
Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!
Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.
Hope you enjoy the instance!
Rules
Rules
- Follow the programming.dev instance rules
- Keep content related to programming in some way
- If you're posting long videos try to add in some form of tldr for those who don't want to watch videos
Wormhole
Follow the wormhole through a path of communities [email protected]
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
I've found that it's usually best to keep it iterative if it can be done with a simple data structure, like stack (DFS) or queue (BFS). But that's not always a simple task.
One common case where recursion is actually more natural is post-order tree traversals. For example if you had a tree where every node held a number and you wanted to calculate the sum of each node's descendants. This is natural with recursion because a node is able to directly sum the values returned from recursive calls. Doing this with an explicit stack would be awkward, because you don't usually get to visit a node twice (once to put children on the stack, once again to accumulate the descendants sum).
Like, just look how weird this algorithm is: https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/ I don't think I've ever done it this way.