CODEWITHSUNDEEP
recursionlinked-liststack
Nishant Joshi
Nishant Joshi

Reputation: 23

Is explicit stack better than recursion

We can print a linked list in reverse order with a stack as well as using recursion. My teacher said that using explicit stack is better since recursion also uses stack but has to maintain a lot of other parameters. Even if we use std::stack from stack, doesn't referring to an external library also take up time? How does using an explicit stack save time/space compared to using a recursive solution?

Upvotes: 2

Views: 2055

Answers (1)

abhijit gupta
abhijit gupta

Reputation: 196

Recursion involves the use of implicit stacks. This is implemented in the background by the compiler being used to compile your code. This background stack created by the compiler is known as a ‘Call stack’. Call Stack can be implemented using stack data structure which stores information about the active subroutines of a computer program.

Each subroutine call uses a frame inside the call stack called the stack frame. When a function returns a value, it’s stack frame is popped off the call stack.

Recursion's Call Stack vs Explicit Call Stack?

Stack overflow

The fundamental difference between the 2 stacks is that the space allocated by the compiler for the call stack of a program is fixed. This means there will be a stack overflow if you’re not sure about the maximum no. of recursive function calls expected and there are way too many calls than the space allocated to the stack can handle at a given point of time. On the other hand, if you define an explicit stack, it’s implemented on the heap space allocated to the program by the compiler at run time. And guess what, the heap size is not fixed and can increase dynamically during run-time when required. You don’t really have to worry about the explicit stack overflowing.

Space and Time

Which one will be faster for a given situation? Iterating on an explicit stack can be faster than recursion in languages that don’t support recursion related optimizations such as tail call optimization for tail recursion.

What’s Tail recursion?

Tail recursion is a special case of recursion where the recursive function doesn’t do any more computation after the recursive function call i.e. the last step of the function is a call to the recursive function.

What’s Tail-call optimization (TCO)?

Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function.

So, compilers/languages that support tail-call optimizations implement the call to the recursive function with only a single stack frame in the call stack. If your compiler/language doesn’t support this, then using an explicit stack will save you a LOT of space and time.

Python doesn’t support tail call optimization. The main reason for this is to have a complete and clear stack trace which enables efficient debugging. Almost all C/C++ compilers support tail call optimization.

Sometimes explicitly controlling the stack helps simplify things when multiple parameters are being used. whereas, a recursive solution makes the size of the source code a lot smaller and more maintainable.

Conclusion

In the end, There’s no fixed answer. For a particular scenario, many factors need to be considered such as scalability, code maintainability, language/compiler being used, etc. The best way would be to implement the solution using both ways, time the 2 solutions on an input set and analyze peak space utilization before deploying it on a production setup.

See Wikipedia - Recursion versus Iteration

Upvotes: 2

Related Questions