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.
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 😄
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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.
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 😄