DEV Community


Discussion on: Recursion - what, why & how

aminmansuri profile image

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
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
return sum(n-1,total+n)

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

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 😄