difference between recursive function and using a stack in terms of use of memory

I want t开发者_JAVA百科o know difference between recursive function and using a stack in terms of use of memory usage. Say for large DFS which will be more efficient.

An explicit stack data structure should use slightly less memory in theory, as a recursive function will always have some additional overhead per invocation, for return address, etc.

I will assume you want to discuss the difference between two approaches of the same algorithm. We have a graph G = (V, E) where V is a set of vertices and E is a set of vertex pairs and we run a depth-first-search (DFS) on the graph by either:

• Using a recursive approach where the visit method recursively calls itself.
• Using an explicit stack in a loop.

Both methods, on the large, use the same amount of space, O(d) where d is the depth of the DFS search tree (it is bounded by the longest possible non-cycling path in the graph.

Usually an explicit stack will use slightly less memory as Paul R writes. Another important point is that in many languages, the function call-stack is severely limited and will abort the program if it grows too large. The explicit stack, managed in the heap, does not pose a similar problem. To get the slightly less memory usage though, you will have to represent the stack as an array though. If you represent it as a linked list, it will probably not be better. It may even be slightly worse.

I'm going to go the other way, at least in compiled languages. Recursive functions, written with an eye to efficieny, can do better than an explicit stack. A compiler can use the stack-frame-manipulation primitives of CPUs that possess them to do things more efficiently.

This view is supported by "Garbage collection is fast, but a stack is faster", by James S Miller and Guillermo Rosaz: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.2789