Recursive Code

Discussion in 'C++' started by cplusplusquestion@gmail.com, Jun 18, 2008.

  1. Guest

    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?
    , Jun 18, 2008
    #1
    1. Advertising

  2. anon Guest

    wrote:
    > 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

    > thing? Change to not recursive seems very difficult. Is there any
    > suggestion for that?
    anon, Jun 18, 2008
    #2
    1. Advertising

  3. Ian Collins Guest

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

    --
    Ian Collins.
    Ian Collins, Jun 18, 2008
    #3
  4. Guest

    On Jun 18, 6:01 pm, Ian Collins <> wrote:

    > 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?
    , Jun 18, 2008
    #4
  5. Ian Collins Guest

    wrote:
    > On Jun 18, 6:01 pm, Ian Collins <> wrote:
    >
    >> 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?


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

    --
    Ian Collins.
    Ian Collins, Jun 18, 2008
    #5
  6. Guest

    > 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++){
    , Jun 18, 2008
    #6
  7. Guest

    On Jun 18, 6:22 pm, wrote:
    > > 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++){
    ....
    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.
    , Jun 18, 2008
    #7
  8. Lionel B Guest

    On Wed, 18 Jun 2008 01:25:51 -0700, cplusplusquestion wrote:

    > On Jun 18, 6:22 pm, wrote:
    >> > 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++){
    > ....
    > 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.

    --
    Lionel B
    Lionel B, Jun 18, 2008
    #8
  9. anon Guest

    wrote:
    > On Jun 18, 6:22 pm, wrote:
    >>> 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++){
    > ....
    > 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?
    anon, Jun 18, 2008
    #9
  10. Guest

    On Jun 18, 7:17 pm, anon <> wrote:
    > wrote:
    > > On Jun 18, 6:22 pm, wrote:
    > >>> 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++){
    > > ....
    > > 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?


    It seems what I want it. I will try this one then. Thanks!
    , Jun 18, 2008
    #10
  11. Guest

    On Jun 18, 7:17 pm, anon <> wrote:
    > wrote:
    > > On Jun 18, 6:22 pm, wrote:
    > >>> 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++){
    > > ....
    > > 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?


    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?
    , Jun 18, 2008
    #11
  12. Guest

    > 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.
    , Jun 18, 2008
    #12
  13. Ian Collins Guest

    wrote:
    > On Jun 18, 7:17 pm, anon <> wrote:
    >> wrote:
    >>> On Jun 18, 6:22 pm, wrote:
    >>>>> 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++){
    >>> ....
    >>> 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?

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

    --
    Ian Collins.
    Ian Collins, Jun 18, 2008
    #13
  14. joseph cook Guest

    On Jun 18, 4:25 am, wrote:
    > On Jun 18, 6:22 pm, wrote:> > 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++){
    >        ....
    >        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
    joseph cook, Jun 18, 2008
    #14
  15. Daniel Pitts Guest

    wrote:
    > On Jun 18, 6:22 pm, wrote:
    >>> 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++){
    > ....
    > 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..



    --
    Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
    Daniel Pitts, Jun 18, 2008
    #15
  16. Guest

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


    The code likes:

    void fun(Array a){
    for(int i=0; i<MAX; i++){
    ....
    if(a != -1) {
    a = -1;
    fun(a);
    }
    }
    }
    , Jun 19, 2008
    #16
  17. joseph cook Guest

    > > 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
    joseph cook, Jun 19, 2008
    #17
  18. Boris Guest

    On Wed, 18 Jun 2008 10:09:33 +0200, <> wrote:

    > On Jun 18, 6:01 pm, Ian Collins <> wrote:
    >
    >> 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?


    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
    Boris, Jun 19, 2008
    #18
  19. Guest

    On 18 Jun., 08:28, wrote:
    > 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.
    , Jun 19, 2008
    #19
  20. Guest

    >
    > 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?
    , Jun 19, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Einar ?rn

    detect recursive C code

    Einar ?rn, Oct 28, 2004, in forum: C Programming
    Replies:
    0
    Views:
    316
    Einar ?rn
    Oct 28, 2004
  2. Einar ?rn

    detect recursive C code

    Einar ?rn, Oct 28, 2004, in forum: C Programming
    Replies:
    6
    Views:
    1,014
    Dave Thompson
    Nov 10, 2004
  3. n00m
    Replies:
    12
    Views:
    1,113
  4. vamsi
    Replies:
    21
    Views:
    2,073
    Keith Thompson
    Mar 9, 2009
  5. capitan
    Replies:
    3
    Views:
    1,999
    capitan
    Sep 25, 2011
Loading...

Share This Page