Recursive Code

[cplusplusquestion]

I've got a recursive function, but the problem is that I need to use a
very big data to test it. Always my program goes to segmentation
fault. Does the problem for RECURSIVE FUNCTION comes with memory
thing? Change to not recursive seems very difficult. Is there any
suggestion for that?

 

[anon]

I've got a recursive function, but the problem is that I need to use a
very big data to test it. Always my program goes to segmentation
fault. Does the problem for RECURSIVE FUNCTION comes with memory

Sound like you are corrupting the memory. You can check your program
with memory checker like valgrind

 

[Ian Collins]

I've got a recursive function, but the problem is that I need to use a
very big data to test it. Always my program goes to segmentation
fault. Does the problem for RECURSIVE FUNCTION comes with memory
thing? Change to not recursive seems very difficult. Is there any
suggestion for that?

You could be running out of stack (too many recursions). Run your
application under a debugger and see where it fails.

 

[cplusplusquestion]

You could be running out of stack (too many recursions). Run your
application under a debugger and see where it fails.

Yes. I guess it runs out of stack. But my problems are: too difficult
to change the code into non recursive. Any suggestion to reduce use
the stack or reuse the stack?

 

[Ian Collins]

Yes. I guess it runs out of stack. But my problems are: too difficult
to change the code into non recursive. Any suggestion to reduce use
the stack or reuse the stack?

Use dynamic allocation where you can. It's hard to give decent advice
without seeing the code.

 

[cplusplusquestion]

Use dynamic allocation where you can. It's hard to give decent advice

without seeing the code.

My code like:

void fun(Array a){
for(int i=0; i<MAX; i++){

 

[cplusplusquestion]

My code like:

void fun(Array a){
for(int i=0; i<MAX; i++){
....
a = ...;
fun(a);
}
}

Here, "Array a" will updated each time and I need "Array a" keeps
previous status, so dynamic allocation for "Array a" does not work.

 

[Lionel B]

My code like:

void fun(Array a){
for(int i=0; i<MAX; i++){
....
a = ...;
fun(a);
}
}

Here, "Array a" will updated each time and I need "Array a" keeps
previous status, so dynamic allocation for "Array a" does not work.

Perhaps you could implement the recursion with your own stack - e.g.
based on std::stack, which will by default use dynamic allocation - as
opposed to the function call stack. This should not be too tricky, as the
algorithm will be essentially the same: just push context (your Array)
when you would call the recursive function, pop context when you would
return.

 

[anon]

My code like:

void fun(Array a){
for(int i=0; i<MAX; i++){
....
a = ...;
fun(a);
}
}

Here, "Array a" will updated each time and I need "Array a" keeps
previous status, so dynamic allocation for "Array a" does not work.

void fun(Array *a)
{
for(int i=0; i<MAX; i++){
....
std::auto_ptr< Array > b( new Array(a) );
fun(b.get());
}
}

Would this work?

 

[cplusplusquestion]

void fun(Array *a)
{
for(int i=0; i<MAX; i++){
....
std::auto_ptr< Array > b( new Array(a) );
fun(b.get());
}

}

Would this work?

It seems what I want it. I will try this one then. Thanks!

 

[cplusplusquestion]

void fun(Array *a)
{
for(int i=0; i<MAX; i++){
....
std::auto_ptr< Array > b( new Array(a) );
fun(b.get());
}

}

Would this work?

I just think that each time new Array(a) will need another memory
allocation, but I need to keep the previous "Array a" value, so that
allocated a new Array(a), I can't delete old one, therefore in this
case, more and more allocations in heap. Am I right?

 

[cplusplusquestion]

Perhaps you could implement the recursion with your own stack - e.g.

based on std::stack, which will by default use dynamic allocation - as
opposed to the function call stack. This should not be too tricky, as the
algorithm will be essentially the same: just push context (your Array)
when you would call the recursive function, pop context when you would
return.

If you could give me some example, it would be appreciated. As I
think, at the end of recursion, "Array a" will be cleared from stack
and function will go back to previous recursion.

 

[Ian Collins]

I just think that each time new Array(a) will need another memory
allocation, but I need to keep the previous "Array a" value, so that
allocated a new Array(a), I can't delete old one, therefore in this
case, more and more allocations in heap. Am I right?

std::auto_ptr will delete each one as it goes out of scope. You will
use the same amount of memory as before (with a on the stack), but it
will come from the heap rather than the stack.

 

[joseph cook]

On Jun 18, 6:22 pm, (e-mail address removed) wrote:> > Use dynamic allocation where you can.  It's hard to give decent advice

My code like:

void fun(Array a){
   for(int i=0; i<MAX; i++){
       ....
       a = ...;
       fun(a);
   }

}

Here, "Array a" will updated each time and I need "Array a" keeps
previous status, so dynamic allocation for "Array a" does not work.

I'm assuming that you have some sort of break condition in that loop,
or it sure as heck will blow out the function stack on any machine
pretty quickly.

Do you really need MAX*MAX*MAX, etc _unique_ copies of this array?
Everything about this smells. Post more code, and I bet a dollar a
better solution can be found for you.

You are passing "Array" by value, so this construct really feels a lot
like tail recursion (since whatever you did inside "fun()" is not
going to propagate back up the call stack). Unless "Array" has
semantics that don't involve a deep copy.

Joe Cook

 

[Daniel Pitts]

My code like:

void fun(Array a){
for(int i=0; i<MAX; i++){
....
a = ...;
fun(a);
}
}

Here, "Array a" will updated each time and I need "Array a" keeps
previous status, so dynamic allocation for "Array a" does not work.

What is your stop condition? It looks like infinite recursion to me..

 

[cplusplusquestion]

What is your stop condition? It looks like infinite recursion to me..

The code likes:

void fun(Array a){
for(int i=0; i<MAX; i++){
....
if(a != -1) {
a = -1;
fun(a);
}
}
}

 

[joseph cook]

What is your stop condition? It looks like infinite recursion to me..

The code likes:

void fun(Array a){
    for(int i=0; i<MAX; i++){
      ....
      if(a != -1) {
         a = -1;
         fun(a);
      }
    }
}

Well..that's interesting. It looks like fun(a) should be called 2^MAX
- 1 times, but any one branch is only "MAX" deep.

So, that would mean that if you are running out of stack (because max

100, say) then this is only a small part of your problem, since your

program will never complete trying to do 2^100 - 1 function calls.
(At least not within a few quadrillion years)

Joe Cook

 

[Boris]

Yes. I guess it runs out of stack. But my problems are: too difficult
to change the code into non recursive. Any suggestion to reduce use
the stack or reuse the stack?

If you are on Windows you can change the stack limit in your executable
with editbin (see
http://msdn.microsoft.com/en-us/library/35yc2tc3(VS.80).aspx) or a linker
option (depends on the linker of course; if you use VC++ there is a linker
option somewhere). This might help you to find out if it's really a
problem with the stack size.

Boris

 

[thomas.mertes]

I've got a recursive function, but the problem is that I need to use a
very big data to test it. Always my program goes to segmentation
fault. Does the problem for RECURSIVE FUNCTION comes with memory
thing? Change to not recursive seems very difficult. Is there any
suggestion for that?

Does a test work with less data?
Have you checked the place of the segfault with a debugger?
IMHO it can be helpful to prove that your theory about,
the recursion running out of stack memory, is correct.

I had cases where I searched for a recursion problem and
the real reason for the error was something else...

Greetings Thomas Mertes

Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[cplusplusquestion]

Does a test work with less data?
Have you checked the place of the segfault with a debugger?
IMHO it can be helpful to prove that your theory about,
the recursion running out of stack memory, is correct.

Thanks. It works fine for less data. You are right, I found the
problem comes from running out of stack memory. However, because my
program is very complicated, it is hard for me to change to not
recursive. I just wonder if there are some other solutions? Or have
any idea to change recursive to not recursive?