6 ms·

Is there a good example of a time where recursion would be much more efficient than iteration?

ur-whale 7y ago
When thinking about hard problems, recursion is often much more efficient than iteration.
saagarjha 7y ago
Recursion is efficient in developer time: it saves you from having to keep track of context yourself because you can just stick it on the call stack.
Merad 7y ago
I'm doubtful that recursion would ever be more performant than iteration. Iteration with a stack gives you all the capability of recursion without the function call overhead. As others have said, the main advantage of recursion is ease of designing and understanding the solution.
rileytg 7y ago
not necessarily efficient but here’s my latest use case: scheduling a health check job recursively. if the health check fails, it schedules itself to run again in X seconds with N-1 runs until giving up and marking the service as down. iteration here simply wouldn’t work
- bananasbandanas 7y ago
  Why not? Just schedule a single health check with a loop that tries to health-check N times in a loop, with a delay in between. If the check succeeds at any point, return 'healthy' early. Or schedule N health checks at different times, if any check succeeds cancel all others, etc. etc.
SwiftyBug 7y ago
I like to use recursion when I can't predict the number of iterations necessary to do the job. For example, a program that calculates the total size of a folder. With recursion I can easily iterate through all levels of the tree and get their sizes. I've used the same approach recently when I wrote a GraphQL query generator in Swift. I recursively iterate through an array of dictionaries, each being able to also hold an array of dictionaries of it's own, each being able to also hold an array of dictionaries of it's own, and so on. In the end all I end up with is single a string. Maybe it's not exactly more efficient, but it was certainly much easier for me.
dreamcompiler 7y ago
I don't know of,a case where it's more efficient, but tail recursion is exactly as efficient as iteration, because they compile to the same code. No stack is used and there's no function call overhead. But you need a compiler that knows how to compile tail calls.

When thinking about hard problems, recursion is often much more efficient than iteration.

Recursion is efficient in developer time: it saves you from having to keep track of context yourself because you can just stick it on the call stack.

Merad 7y ago

I'm doubtful that recursion would ever be more performant than iteration. Iteration with a stack gives you all the capability of recursion without the function call overhead. As others have said, the main advantage of recursion is ease of designing and understanding the solution.

rileytg 7y ago

not necessarily efficient but here’s my latest use case: scheduling a health check job recursively. if the health check fails, it schedules itself to run again in X seconds with N-1 runs until giving up and marking the service as down. iteration here simply wouldn’t work

bananasbandanas 7y ago
Why not? Just schedule a single health check with a loop that tries to health-check N times in a loop, with a delay in between. If the check succeeds at any point, return 'healthy' early. Or schedule N health checks at different times, if any check succeeds cancel all others, etc. etc.

SwiftyBug 7y ago

I like to use recursion when I can't predict the number of iterations necessary to do the job. For example, a program that calculates the total size of a folder. With recursion I can easily iterate through all levels of the tree and get their sizes. I've used the same approach recently when I wrote a GraphQL query generator in Swift. I recursively iterate through an array of dictionaries, each being able to also hold an array of dictionaries of it's own, each being able to also hold an array of dictionaries of it's own, and so on. In the end all I end up with is single a string. Maybe it's not exactly more efficient, but it was certainly much easier for me.

dreamcompiler 7y ago

I don't know of,a case where it's more efficient, but tail recursion is exactly as efficient as iteration, because they compile to the same code. No stack is used and there's no function call overhead. But you need a compiler that knows how to compile tail calls.