Recursing code problem

Discussion in 'C Programming' started by snowdy, Aug 29, 2003.

  1. snowdy

    snowdy Guest

    I am using Interactive C with my handboard (68HC11) development system but
    I've got a problem that I am asking for help with.
    I am not new to C but learning all the time and I just cant see how to
    overcome this problem.

    Symptom:
    Programs fail ' Runtime error' which equates to a stack error.
    This is because my code is like going around and around (a snake chasing its
    tail is a term I've seen used) but I cant quite come to grips with how to
    overcome this problem.

    Should I post some of the code up on this group for people with a better
    knowledge of this problem to make suggestions - I feel its probably
    something not difficult to understand but I just need a little guidance
    here.

    Jeff
    snowdy, Aug 29, 2003
    #1
    1. Advertising

  2. snowdy

    Artie Gold Guest

    snowdy wrote:
    > I am using Interactive C with my handboard (68HC11) development system but
    > I've got a problem that I am asking for help with.
    > I am not new to C but learning all the time and I just cant see how to
    > overcome this problem.
    >
    > Symptom:
    > Programs fail ' Runtime error' which equates to a stack error.
    > This is because my code is like going around and around (a snake chasing its
    > tail is a term I've seen used) but I cant quite come to grips with how to
    > overcome this problem.
    >
    > Should I post some of the code up on this group for people with a better
    > knowledge of this problem to make suggestions - I feel its probably
    > something not difficult to understand but I just need a little guidance
    > here.
    >

    Post the smallest compilable snippet that exhibits the problem you're
    having.

    HTH,
    --ag




    --
    Artie Gold -- Austin, Texas
    Artie Gold, Aug 29, 2003
    #2
    1. Advertising

  3. snowdy wrote:
    >
    > I am using Interactive C with my handboard (68HC11) development system but
    > I've got a problem that I am asking for help with.
    > I am not new to C but learning all the time and I just cant see how to
    > overcome this problem.
    >
    > Symptom:
    > Programs fail ' Runtime error' which equates to a stack error.
    > This is because my code is like going around and around (a snake chasing its
    > tail is a term I've seen used) but I cant quite come to grips with how to
    > overcome this problem.
    >
    > Should I post some of the code up on this group for people with a better
    > knowledge of this problem to make suggestions - I feel its probably
    > something not difficult to understand but I just need a little guidance
    > here.
    >
    > Jeff


    Post some code. However, your symptoms sound like you don't
    have a proper termination condition. One problem with recursive
    code (and I use it a lot and even wrote a column about it) is that
    it is easy to create an endless loop that overwrites the stack.

    Also, some problems are not well-suited to recursion: the stack
    gets too deep and boom! So you ought to analyze your code to
    estimate how the stack-depth grows with problem size.

    You can find my column, Recurses!, at

    http://www.phys.virginia.edu/classes/551.jvn.fall01/CiSE_progs/Cprogs.htm

    --
    Julian V. Noble
    Professor Emeritus of Physics

    ^^^^^^^^^^^^^^^^^^
    http://galileo.phys.virginia.edu/~jvn/

    "Science knows only one commandment: contribute to science."
    -- Bertolt Brecht, "Galileo".
    Julian V. Noble, Aug 29, 2003
    #3
  4. snowdy

    ArWeGod Guest

    "snowdy" <@nospam> wrote in message
    news:3f4f4da8$0$4191$...
    ....snip...
    > Symptom:
    > Programs fail ' Runtime error' which equates to a stack error.
    > This is because my code is like going around and around (a snake chasing

    its
    > tail is a term I've seen used) but I cant quite come to grips with how to
    > overcome this problem.


    ....snip...
    > Jeff


    I've also run into this problem. Here's something simple to try:
    ==============================
    /*
    factorial.c
    Takes one command-line argument: the number you want the factorial of.
    Breaks at around 39! with the following:
    run-time error R6000
    - stack overflow
    */

    #include <stdio.h>
    #include <stdlib.h>

    double fact (int n);

    void main(int argc, char **argv)
    {
    int n;
    double factorial=1;

    n = atoi (argv[1]);
    fact (n);
    }

    double fact (int n)
    {
    static double value=1;

    if (n > 1)
    value = n * fact (n-1);

    printf ("%3.d! = %.0f \n", n, value);

    return (value);
    }

    ==============================

    So, I have the same question. How can I increase the stack or otherwise make
    this work for higher numbers?

    --
    ArWeGod
    ArWeGod, Aug 29, 2003
    #4
  5. snowdy

    Malcolm Guest

    "ArWeGod" <> wrote in message
    >
    > /*
    > factorial.c
    > Takes one command-line argument: the number you want the factorial > of.
    > Breaks at around 39! with the following:
    > run-time error R6000
    > - stack overflow
    > */
    >
    >
    > double fact (int n)
    > {
    > static double value=1;
    >
    > if (n > 1)
    > value = n * fact (n-1);
    >
    > printf ("%3.d! = %.0f \n", n, value);
    >
    > return (value);
    > }
    >
    > So, I have the same question. How can I increase the stack or
    > otherwise make this work for higher numbers?
    >


    This surprises me, because even a relatively puny stack shouldn't overflow
    at a depth of 39 functions.
    What will overflow quite rapidly is the precision of a double.
    Malcolm, Aug 29, 2003
    #5
  6. snowdy

    Neil Cerutti Guest

    In article <>, Eric Sosman wrote:
    ><rant topicality="zero">
    > Why do people so often talk about factorials or the Fibonacci
    > numbers when explaining recursion? Neither is well- suited to
    > a recursive solution; iteration wins on practically every
    > measure. And for the Fibonacci numbers, iteration itself is
    > easily beatable; recursion is at best a poor third choice. But
    > look up any textbook or lecture about recursion, and what do
    > you find? Factorials and Fibonacci! Foolishness!
    >
    ></rant>


    Because factorials and fibonacci number's make such wonderfully
    simple recursive functions. The crappyness of the resulting
    solutions isn't a consideration when the intent is to educate.

    A program that is "best" written recursively, like a program that
    shows all the possible ways to make a certain amount of change,
    may be too complicated for an introduction to recursion.

    <rant> I think the word "recursion" should be abolished from
    primmers. It just creates consternation. I could create a similar
    effect by constantly using the word "ambulation" to describe the
    act of going for a walk. </rant>

    --
    Neil Cerutti
    Neil Cerutti, Aug 29, 2003
    #6
  7. snowdy

    Alan Balmer Guest

    On Fri, 29 Aug 2003 15:40:33 -0400, Eric Sosman <>
    wrote:

    > Why do people so often talk about factorials or the
    >Fibonacci numbers when explaining recursion?


    For the same reason they talk about the bubble sort when introducing
    sorting - it's easily understood.

    --
    Al Balmer
    Balmer Consulting
    Alan Balmer, Aug 29, 2003
    #7
  8. "Neil Cerutti" <> wrote in message
    news:bioclr$b2kvo$-berlin.de...

    (snip regarding recursive functions)

    > <rant> I think the word "recursion" should be abolished from
    > primmers. It just creates consternation. I could create a similar
    > effect by constantly using the word "ambulation" to describe the
    > act of going for a walk. </rant>


    How about reentrant, which isn't quite the same, but related.

    Along the same line, there is refreshable and serially reusable.

    -- glen
    Glen Herrmannsfeldt, Aug 29, 2003
    #8
  9. snowdy

    ArWeGod Guest

    "Malcolm" <> wrote in message
    news:biobih$vao$...
    >
    > "ArWeGod" <> wrote in message
    > >
    > > /*
    > > factorial.c
    > > Takes one command-line argument: the number you want the factorial > of.
    > > Breaks at around 39! with the following:
    > > run-time error R6000
    > > - stack overflow
    > > */
    > >
    > >
    > > double fact (int n)
    > > {
    > > static double value=1;
    > >
    > > if (n > 1)
    > > value = n * fact (n-1);
    > >
    > > printf ("%3.d! = %.0f \n", n, value);
    > >
    > > return (value);
    > > }
    > >
    > > So, I have the same question. How can I increase the stack or
    > > otherwise make this work for higher numbers?
    > >

    >
    > This surprises me, because even a relatively puny stack shouldn't overflow
    > at a depth of 39 functions.
    > What will overflow quite rapidly is the precision of a double.
    >


    You may have hit the nail on the head.
    The value I get for 38! is 523022617466601000000000000000000000000000000.

    Q1. Anybody know the limit of a double?

    Q2. Anybody know of a bigger number - holder? long double? unsigned double?
    etc.

    I guess for this sort of thing you need to do your number handling for
    overflow, etc.

    --
    ArWeGod
    ArWeGod, Aug 29, 2003
    #9
  10. snowdy

    Alan Balmer Guest

    On Fri, 29 Aug 2003 22:43:33 GMT, "ArWeGod" <>
    wrote:

    >> This surprises me, because even a relatively puny stack shouldn't overflow
    >> at a depth of 39 functions.
    >> What will overflow quite rapidly is the precision of a double.
    >>

    >
    >You may have hit the nail on the head.
    >The value I get for 38! is 523022617466601000000000000000000000000000000.

    That won't cause a stack overflow.
    >
    >Q1. Anybody know the limit of a double?

    Implementation dependent.
    >
    >Q2. Anybody know of a bigger number - holder? long double? unsigned double?
    >etc.

    Google for "big number" packages.


    BTW, I just read your classification of programmers from newby to 5+
    years. Apparently that was from observation, not practice?

    --
    Al Balmer
    Balmer Consulting
    Alan Balmer, Aug 30, 2003
    #10
  11. snowdy

    Ben Pfaff Guest

    "ArWeGod" <> writes:

    > Q1. Anybody know the limit of a double?


    DBL_MAX
    --
    A competent C programmer knows how to write C programs correctly,
    a C expert knows enough to argue with Dan Pop, and a C expert
    expert knows not to bother.
    Ben Pfaff, Aug 30, 2003
    #11
  12. snowdy

    ArWeGod Guest

    "Ben Pfaff" <> wrote in message
    news:...
    > "ArWeGod" <> writes:
    >
    > > Q1. Anybody know the limit of a double?

    >
    > DBL_MAX


    So, is

    #define DBL_MAX 1.7976931348623158e+308 /* max value */ // my MSVC
    compiler's value

    more than

    523022617466601000000000000000000000000000000 * 39?

    ....I _think_ I get an overflow error. If not it's a recursion problem. You
    tell me. I'm NOT going to do the math - I have a few critics - you work it
    out!

    But, please, don't attack me, just post the correct answer to help
    everybody. I don't really care - I've never calculated factorials, I just
    wrote the program because it was asked it on a job interview and I was
    checking my work.

    ;-)

    --
    ArWeGod
    ArWeGod, Aug 30, 2003
    #12
  13. snowdy

    Ben Pfaff Guest

    "ArWeGod" <> writes:

    > "Ben Pfaff" <> wrote in message
    > news:...
    > > "ArWeGod" <> writes:
    > >
    > > > Q1. Anybody know the limit of a double?

    > >
    > > DBL_MAX

    >
    > So, is
    >
    > #define DBL_MAX 1.7976931348623158e+308 /* max value */ // my MSVC
    > compiler's value
    >
    > more than
    >
    > 523022617466601000000000000000000000000000000 * 39?


    Yes. Written out in full, 1.7976931348623158e+308 is
    179769313486231580000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000,
    more than a googol times larger than
    523022617466601000000000000000000000000000000 * 39.

    I don't know what your exact problem is, not having examined the
    situation closely. Floating-point calculations are notoriously
    tricky. But the problem should not be one of overflow.

    --
    "I hope, some day, to learn to read.
    It seems to be even harder than writing."
    --Richard Heathfield
    Ben Pfaff, Aug 30, 2003
    #13
  14. snowdy

    pete Guest

    R. Rajesh Jeba Anbiah wrote:
    >
    > Eric Sosman <> wrote in message news:<>...
    > > Why do people so often talk about factorials or the
    > > Fibonacci numbers when explaining recursion? Neither is well-
    > > suited to a recursive solution; iteration wins on practically
    > > every measure. And for the Fibonacci numbers, iteration itself
    > > is easily beatable; recursion is at best a poor third choice.
    > > But look up any textbook or lecture about recursion, and what
    > > do you find? Factorials and Fibonacci! Foolishness!

    >
    > Factorials and Fibonacci are dealt only in beginner/intermediate
    > level books. That is because, it is easier to convey the recursive
    > logic via these simple Factorials and Fibonacci.
    >
    > Professor has mentioned his recursive programs of
    > http://www.phys.virginia.edu/classes/551.jvn.fall01/CiSE_progs/Cprogs.htm
    > But, most of the programs that he mentioned won't be suited to explain
    > the recursive logic in simple beginners' book.


    The 8 queens problem seems to be a good one to me for recursion,
    but that's the only one that I know.

    --
    pete
    pete, Aug 30, 2003
    #14
  15. Eric Sosman wrote:
    >
    > ArWeGod wrote:
    > >
    > > I've also run into this problem. Here's something simple to try:
    > > [... recursive computation of factorial snipped ...]
    > >
    > > So, I have the same question. How can I increase the stack or otherwise make
    > > this work for higher numbers?

    >
    > It is possible to express any recursive computation in
    > iterative form, but that doesn't mean iteration is always
    > the best technique to use. It is possible to express any
    > iterative computation in recursive form, but that doesn't
    > mean recursion is always the best technique to use.
    >
    > If you need to compute factorials (an iffy business
    > at best, by the way), iteration is a better approach than
    > recursion.
    >
    > <rant topicality="zero">
    >
    > Why do people so often talk about factorials or the
    > Fibonacci numbers when explaining recursion? Neither is well-
    > suited to a recursive solution; iteration wins on practically
    > every measure. And for the Fibonacci numbers, iteration itself
    > is easily beatable; recursion is at best a poor third choice.
    > But look up any textbook or lecture about recursion, and what
    > do you find? Factorials and Fibonacci! Foolishness!
    >
    > </rant>


    Quite right. In my column "Recurses!" I said essentially the same thing.
    Another frequently used example that is almost as bad is string
    reversal. Here is an example in M$ QuickBASIC:

    FUNCTION rev$ (a$)
    c$ = MID$(a$, 1, 1)
    IF c$ = "" THEN
    rev$ = ""
    ELSE
    rev$ = rev$(MID$(a$, 2)) + c$
    END IF
    END FUNCTION

    I am sure there must be C versions floating around but I haven't
    time to look for one or to translate the above. Someday...


    --
    Julian V. Noble
    Professor Emeritus of Physics

    ^^^^^^^^^^^^^^^^^^
    http://galileo.phys.virginia.edu/~jvn/

    "Science knows only one commandment: contribute to science."
    -- Bertolt Brecht, "Galileo".
    Julian V. Noble, Aug 30, 2003
    #15
  16. Julian V. Noble <> scribbled the following:
    > Quite right. In my column "Recurses!" I said essentially the same thing.
    > Another frequently used example that is almost as bad is string
    > reversal. Here is an example in M$ QuickBASIC:


    > FUNCTION rev$ (a$)
    > c$ = MID$(a$, 1, 1)


    This would be more readable as:
    c$ = LEFT$(a$, 1)

    > IF c$ = "" THEN
    > rev$ = ""
    > ELSE
    > rev$ = rev$(MID$(a$, 2)) + c$
    > END IF
    > END FUNCTION


    --
    /-- Joona Palaste () ---------------------------\
    | Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
    | http://www.helsinki.fi/~palaste W++ B OP+ |
    \----------------------------------------- Finland rules! ------------/
    "C++. C++ run. Run, ++, run."
    - JIPsoft
    Joona I Palaste, Aug 31, 2003
    #16
  17. On Sat, 30 Aug 2003, Randy Howard wrote:
    >
    > In article <>, says...
    > > <rant topicality="zero">

    >
    > While we're here, a joke...
    >
    > "Knock, Knock"
    > "Who's there?"
    > "Recursion."
    > "Recursion who?"
    >
    > "Knock, Knock"
    > ...


    No, no, no! ;-)

    "Knock, knock."
    "Who's there?"
    "Iteration."
    "Iteration who?"
    "Knock knock."
    "Who's there?"
    "Iteration."
    "Iteration who?"
    "Knock knock."
    "Who's there?"
    "Orange."
    "Orange who?..."


    "Knock knock."
    "Who's there?"
    "Recursion."
    "Recursion who?"
    "Recursion knock knock."
    "Recursion knock knock who?"
    "Recursion knock knock knock."
    "Who's there?..."

    -Arthur
    Arthur J. O'Dwyer, Aug 31, 2003
    #17
  18. snowdy

    Paul Hsieh Guest

    Eric Sosman <> wrote:
    > <rant topicality="zero">
    >
    > Why do people so often talk about factorials or the
    > Fibonacci numbers when explaining recursion? Neither is well-
    > suited to a recursive solution; iteration wins on practically
    > every measure.


    Not necessarily so. The following is a re-expression of the fibonacci
    sequence recursive formula:

    f[0] = 0
    f[1] = 1
    f[2] = 1
    f[n] = f[(n+1)/2]^2 + f[(n-1)/2]^2 ; if n is odd
    = f[n/2+1]^2 - f[n/2-1]^2 ; if n is even

    Which implies a recursion of depth about ln(n) steps. Now if you do
    the math, you will realize that the total number of calls does in fact
    lead to O(n) which might lead you to believe that iterative is faster
    (since its less complicated). However, if you cache the values as you
    compute them, then this should run in about O((ln(n))^2) which should
    *SKUNK* the iterative solution for large enough n.

    > [...] And for the Fibonacci numbers, iteration itself
    > is easily beatable;


    By a complete table look up of course! (No this will not blow out your
    memory; think about it.)

    > [...] recursion is at best a poor third choice.


    As I pointed out above, depends on which recursive formula you are
    talking about.

    > But look up any textbook or lecture about recursion, and what
    > do you find? Factorials and Fibonacci! Foolishness!


    They are the easiest examples -- they can't explain trees until they
    explain recursion.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
    Paul Hsieh, Aug 31, 2003
    #18
  19. (Paul Hsieh) writes:

    > Eric Sosman <> wrote:
    >
    > > And for the Fibonacci numbers, iteration itself is easily beatable;

    >
    > By a complete table look up of course!


    One easy way to calculate the `n'-th Fibonacci number `f' without a table
    is this:

    const double sqrt5 = sqrt (5.0);
    const double golden = 0.5 + 0.5 * sqrt5;

    int f = (int)(pow (golden, (double)n) / sqrt5 + 0.5);

    Martin
    Martin Dickopp, Aug 31, 2003
    #19
  20. On Fri, 29 Aug 2003 22:43:33 GMT, "ArWeGod" <> wrote:
    >The value I get for 38! is 523022617466601000000000000000000000000000000.


    The correct value is 523022617466601111760007224100074291200000000

    You aren't suffering from overflow, but from a loss of precision because a
    double doesn't hold enough bits to represent the correct value.

    (And 39! is 20397882081197443358640281739902897356800000000)

    169! (~4.3e305) is the largest value a double can hold without overflow:

    42690680090047052749392518888995665380688186360567
    36103849163411117977554942180092854323970142716152
    65381823013990501222156824856790750177960523574894
    55946484708413412107621199803603527401512378815048
    78975040568419670360154453585262827477179746400268
    93725894862438400000000000000000000000000000000000
    00000


    --
    #include <standard.disclaimer>
    _
    Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
    Per the FCA, this address may not be added to any commercial mail list
    Kevin D. Quitt, Sep 2, 2003
    #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. Scott Carlson

    recursing through files in a folder

    Scott Carlson, Oct 1, 2004, in forum: Python
    Replies:
    3
    Views:
    362
    Mirko Zeibig
    Oct 1, 2004
  2. Replies:
    4
    Views:
    335
  3. Henrik Goldman

    Recursing macro preprocessing?

    Henrik Goldman, Oct 21, 2006, in forum: C++
    Replies:
    4
    Views:
    370
    Kaz Kylheku
    Oct 22, 2006
  4. Randy

    StackOverFlowException When Recursing Page Controls

    Randy, Jan 18, 2006, in forum: ASP .Net Web Controls
    Replies:
    1
    Views:
    120
    Randy
    Jan 19, 2006
  5. Gabriel Dragffy

    Recursing through directories

    Gabriel Dragffy, Sep 26, 2007, in forum: Ruby
    Replies:
    13
    Views:
    229
    Rob Biedenharn
    Oct 2, 2007
Loading...

Share This Page