DEV Community

loading...

Discussion on: Recursion - what, why & how

Collapse
gypsydave5 profile image
David Wickes

One of the benefits of recursion is it can potentially reduce Big O time.

Could you explain this a bit more? It seems like a pretty big claim, and it doesn't jibe with my understanding of the subject.

Collapse
jacobmgevans profile image
Jacob Evans Author

I'll link the resource when I get a chance to get on my computer.

A quick overview of it would be one way of reducing Big O of time is memoization, however, the cost of Big O memory (which is already high with recursion) increases even further.

Collapse
jacobmgevans profile image
Jacob Evans Author • Edited

I'm also more than happy to be proven wrong, or dive deeper into this together and discover more on it 😁

Collapse
jacobmgevans profile image
Jacob Evans Author • Edited

I couldn't find my previous resource but this has an example of recursion implementing memoization to reduce Big O complexity. It may be that it is possible to memoize the iterative approach as well and it's just easier to utilize recursions use of holding memory to make it easier or more efficient.
stackoverflow.com/questions/134400...