What are the drawbacks of exponential complexity in recursive functions, especially on memory ?!! | Sololearn: Learn to code for FREE!
New course! Every coder should learn Generative AI!
Try a free lesson
+ 1

What are the drawbacks of exponential complexity in recursive functions, especially on memory ?!!

6th Nov 2017, 8:05 PM
Muhammad Fouad Al-Haroon
Muhammad Fouad Al-Haroon - avatar
3 Answers
+ 10
Well, the memory limit itself :) Recursion is very memory-consuming as it stores all its iterations 'in-memory' and frees it only when (or if) it reaches the base case and is "unpacked" and evaluated. Loops, on the other hand, store only the currently iterated value (provided that garbage collection is automatic or resolved somehow).
6th Nov 2017, 8:54 PM
Kuba Siekierzyński
Kuba Siekierzyński - avatar
+ 9
Hmm... Check out this thread below and let me know your thoughts ;) Oh, before you do - imagine if your recursion does that a million times - when will the memory limit be reached? Pretty soon, I gues... In order to be able to return a step back, it has to remember *all* the previous steps (and so yoy can navigate back in my example). And still, when during the recursive loop, you don't get the final result until the very end. "Unpacking" or "unfolding" is a state when the base case is reached and, if properly done, the computed, concrete value is established for that case. It then has to be taken into account for computations in all preceding recursion phases. https://www.sololearn.com/discuss/307407/?ref=app
6th Nov 2017, 9:39 PM
Kuba Siekierzyński
Kuba Siekierzyński - avatar
+ 1
you mean by the iterations in the recursion the recursive calls ?! And what does it mean by unpacked and evaluated ?
6th Nov 2017, 9:28 PM
Muhammad Fouad Al-Haroon
Muhammad Fouad Al-Haroon - avatar