Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Recursing code problem

Reply
Thread Tools

Recursing code problem

 
 
snowdy
Guest
Posts: n/a
 
      08-29-2003
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


 
Reply With Quote
 
 
 
 
Artie Gold
Guest
Posts: n/a
 
      08-29-2003
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

 
Reply With Quote
 
 
 
 
Julian V. Noble
Guest
Posts: n/a
 
      08-29-2003
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...ogs/Cprogs.htm

--
Julian V. Noble
Professor Emeritus of Physics
http://www.velocityreviews.com/forums/(E-Mail Removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".
 
Reply With Quote
 
ArWeGod
Guest
Posts: n/a
 
      08-29-2003
"snowdy" <(E-Mail Removed)@nospam> wrote in message
news:3f4f4da8$0$4191$(E-Mail Removed) ...
....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


 
Reply With Quote
 
Malcolm
Guest
Posts: n/a
 
      08-29-2003

"ArWeGod" <(E-Mail Removed)> 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.


 
Reply With Quote
 
Neil Cerutti
Guest
Posts: n/a
 
      08-29-2003
In article <(E-Mail Removed)>, 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
 
Reply With Quote
 
Alan Balmer
Guest
Posts: n/a
 
      08-29-2003
On Fri, 29 Aug 2003 15:40:33 -0400, Eric Sosman <(E-Mail Removed)>
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
(E-Mail Removed)
 
Reply With Quote
 
Glen Herrmannsfeldt
Guest
Posts: n/a
 
      08-29-2003

"Neil Cerutti" <(E-Mail Removed)> wrote in message
news:bioclr$b2kvo$(E-Mail Removed)-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


 
Reply With Quote
 
ArWeGod
Guest
Posts: n/a
 
      08-29-2003
"Malcolm" <(E-Mail Removed)> wrote in message
news:biobih$vao$(E-Mail Removed)...
>
> "ArWeGod" <(E-Mail Removed)> 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


 
Reply With Quote
 
Alan Balmer
Guest
Posts: n/a
 
      08-29-2003
On Fri, 29 Aug 2003 22:43:33 GMT, "ArWeGod" <(E-Mail Removed)>
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
(E-Mail Removed)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recursing through directories Gabriel Dragffy Ruby 13 10-02-2007 12:07 AM
Recursing macro preprocessing? Henrik Goldman C++ 4 10-22-2006 05:25 AM
Recursing for Progress Bar half.italian@gmail.com Python 4 09-19-2006 04:53 AM
StackOverFlowException When Recursing Page Controls Randy ASP .Net Web Controls 1 01-19-2006 05:02 AM
recursing through files in a folder Scott Carlson Python 3 10-01-2004 05:51 PM



Advertisments