0

We have learnt that in recursion a function calls itself n number of times before a condition is met, and each call gets a place in memory including each variable in that function uses.

With enough number of calls in the call stack recursion would run out of memory.

Mean while loop for this same purpose can reuse the same variables again and again. Which saves a lot of memory.

So why is recursion used??

1

At the machine code level a loop is just a conditional jump and a test whereas a naively implemented recursion involves jumps, stack frame pushes, stack frame pops, and returns.

Howbeit, most recursive functions can be rewritten to avoid stack frame push/pop by exerting tail recursion which yield an equivalent to an iterative loop at the machine code level.

The use of stack frames however might be benefiting in certain scenarios as it allows stack tracebacks, a la debugging; In contrast, a loop employs destructive state update and therefore limits tracebacks.

Furthermore, from a mathematical perspective the recursive approach is preferred as the solutions are well matched to the abstract mathematical entity (i.e. tree data structure).

I am assuming your question is in relation to a C-like language as the answers will vary depending on the language, compiler and the dataset; For a more comprehensive overview refer these slides.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .