Recursive DFS

[Jackson Chung]

I'm aware of Prof. Abdelrahman's announcement that we should use stack and
queue for assignment 6.
However, would someone please explain why recursion is such a bad idea for
implementing the DFS?
Why can't we use recursion for DFS if we have the ability to implement
it and make sure it works?

Thanks,
Jackson Chung

[John C Wu]

Recursion is very memory inefficient. Each time, a recursion call is made,
a chunk of memory space is allocated to handle this function call, and as
more and more recursion calls are made, more memory space is being
allocated. The memory space allocated will not be freed until the recursion
call exits. If we have a graph that has one branch that goes really deep,
then a sigificant amount of memory will be needed to solve the question, and
if the branch is rediculously deep, then you might run out of memory before
getting to the solution. However, by using a stack, we don't have this
problem.

John C Wu

[John Wu]

Recursion is very memory inefficient. Each time, a recursion call is

made, a chunk of memory space is allocated to handle this function call,
and as more and more recursion calls are made, more memory space is being
allocated. The memory space allocated will not be freed until the
recursion call exits. If we have a graph that has one branch that goes
really deep, then a sigificant amount of memory will be needed to solve
the question, and if the branch is rediculously deep, then you might run
out of memory before getting to the solution. However, by using a stack,
we don't have this problem.

.--------..------------..--------..-----------------------..--------.
| o\ /o || John C Wu || o\ /o || Engineering Science || o\ /o |
| ---- || || ---- || University of Toronto || ---- |
`--------'`------------'`--------'`-----------------------'`--------'

"Memory is like an orgasm. It's a lot better if you don't have to fake it."
Seymour Cray commenting on virtual memory

[erik watson-hurthig]

REPRESENT!

erik "thank goodness this term is almost over" wanton

[Mike Czajka]

Isn't a function recursion handled as a stack call internally? And
especially with such a simple recursion call, if we optimize code, the
compiler should be able to figure it out for itself, shouldn't it?

The only really disappointing thing is that the spec that a stack is
REQUIRED is not included in the assignment hand-out.

-Mike

"John Wu" <jo...@ecf.utoronto.ca> wrote in message
news:Pine.SGI.3.96.10104081...@skule.ecf...

[John Wu]

On Mon, 9 Apr 2001, Mike Czajka wrote:

> Isn't a function recursion handled as a stack call internally? And
> especially with such a simple recursion call, if we optimize code, the
> compiler should be able to figure it out for itself, shouldn't it?
>

True. Many compilers these days does this kinda optimization for you.
But it still doesn't hurt to know a bit of the internals. Regarding the
assignment spec, as what I said before, your instructors will have the
final say. My job is just to help you with the assignments.