DEV Community

loading...

Discussion on: Recursion - what, why & how

Collapse
aminmansuri profile image
hidden_dude

I think Recursion is better sometimes because it can make somewhat complex algorithms seem simple. For example, QuickSort or MergeSort are quite easy to express recursively. They are much harder to read when written in non-recursive ways.

The Big-O complexity has little to do with recursion, since anything that can be written recursively can be written non-recursively (though it would look horrible in some cases).

A big danger of recursion is using it in languages that don't optimize away the stack (most popular languages) as well as hidden Big-O memory usage.

For example:

function sum(n) {
if (0 >= n)
return 0
else
return n + sum(n-1)
}

Uses O(N) stack space (assuming a language that optimizes away the stack). Whereas:

function sum(n,total)
if (0>=n)
return total
else
return sum(n-1,total+n)
}

Would use O(1) extra space in a language like Scheme.

Collapse
jacobmgevans profile image
Jacob Evans Author

Well said. I certainly don't consider myself an expert in Big O related things, I just read during my research it can be more efficient than an iterative approach in some instances where memoization can be utilized.

It wasn't 100% clear to me but enough to add it in as a possibility.

Love your comment though very insightful! Thank you 😄