Depth of Recursion with parameters Vs Length of Iteration

[Checkmate]

Hi,

I m woking in Graph algorithms. I am facing some difficulties with
very big graphs.

when I am calling the recursive function with parameters the no. of
calling recursive functions are less than without parameters before
program is terminated with segmentation fault. what is the impact of
argument in recursive function. I am passing vector as my argument.

when I am doing this using my explicit stack by iterative loop it
takes much more time than recursive function for very big graph. is
there any big difference in terms of speed for recursion and
iteration????

-Suhas

 

[Pascal J. Bourguignon]

Hi,

I m woking in Graph algorithms. I am facing some difficulties with
very big graphs.

when I am calling the recursive function with parameters the no. of
calling recursive functions are less than without parameters before
program is terminated with segmentation fault.

It's probable that passing arguments to functions uses stack space.

what is the impact of
argument in recursive function. I am passing vector as my argument.

If you're passing a vector, it will have to be copied probably on the
stack, so you will probably use a lot of stack space for each
recursive call.

when I am doing this using my explicit stack by iterative loop it
takes much more time than recursive function for very big graph. is
there any big difference in terms of speed for recursion and
iteration????

It all depends.

Instead of passing whole vectors to your recursive functions, try to
pass only a pointer or a reference to the vector, thus avoiding
copying it and using up stack space.

As much as possible, try to make your function tail-recursive, so
tail-call-optimization can be implemented (gcc does it), thus avoiding
using up stack space.

 

[Rolf Magnus]

If you're passing a vector, it will have to be copied probably on the
stack, so you will probably use a lot of stack space for each
recursive call.

Typical vector implementations are rather small (in the extreme case one
pointer and two integers).

 

[Erik Wikström]

Typical vector implementations are rather small (in the extreme case one
pointer and two integers).

The real impact comes from copying all the elements in the vector,
unless something like copy on write is used.

 

[James Kanze]

On 2008-12-04 06:14, Rolf Magnus wrote:

The real impact comes from copying all the elements in the
vector, unless something like copy on write is used.

An implementation of std::vector can't use copy on write, since
this would require violating some of the constraints on the
validity of pointers and references into the container.