[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

Depth of Recursion with parameters Vs Length of Iteration

Checkmate

12/3/2008 5:19:00 AM

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
5 Answers

pjb

12/3/2008 1:03:00 PM

0

Checkmate <suhas.genius@gmail.com> writes:

> 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.


--
__Pascal Bourguignon__

Rolf Magnus

12/4/2008 5:14:00 AM

0

Pascal J. Bourguignon wrote:

>> 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.

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

Erik Wikström

12/4/2008 6:27:00 AM

0

On 2008-12-04 06:14, Rolf Magnus wrote:
> Pascal J. Bourguignon wrote:
>
>>> 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.
>
> 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.

--
Erik Wikström

James Kanze

12/4/2008 11:57:00 AM

0

On Dec 4, 7:27 am, Erik Wikström <Erik-wikst...@telia.com> wrote:
> On 2008-12-04 06:14, Rolf Magnus wrote:

> > Pascal J. Bourguignon wrote:

> >>> 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.

> > 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.

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.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

observador

6/11/2011 3:18:00 AM

0


Con las deudas de chavez, ni a mil dolares ed barril lo salva




On Jun 10, 6:39 pm, jat <j...@none.null> wrote:
> On 06/10/2011 07:53 PM, ljsprojects wrote:> Y pensar que Giusti quería mantener el precio por debajo de diez
> > dólares.
> > Supongo que queria destruir la Opep. (Opec en ingles).
> > Eso es lo que querian los dirigentes de Pdvsa antes de Chevez.
> > Es lo que llaman New World Order.
>
> > T.Schmidt
> > P.S. Giusti ha escrito articulos donde defiende la Globalizacion,
> > siempre y cuendo sean los gringos los que manden (parece que vamos a
> > tener la bendita globalizacion, pero con China).
> > Este es Luis Giusti, italiano de Maracaibo. No es el unico, como el
> > eran casi todos los jefes de Pdsva (por eso me vine en 1980). Amigo de
> > Bush, Uribe y su mafia.
>
> >http://csis.org/expert/lui...
>
> Tan inteligentes y tan serviles o simplemente nunca se han sentido
> venezolanos *pitiyankis*
>
> --
> /jat
> Knowledge shall make you free
> El conocimiento te hará libre