tree

[Bill Cunningham]

pgs 140-1 of kandr2 talk about recursion. I tried typing in the code
char by char and couldn't find the bugs so I just read the code and a new
concept to me jumped out. Maybe this is what it means by recursion.

struct tnode *addtree (struct tnode *, char *);

is declared on p 140. But I noticed this on p 141.

struct tnode *addtree (struct tnode *p, char *w);

Can someone explain to me why the parameters are changing here? Would they
need to change more with the program on pages 140-1 ?

Bill

[Ben Bacarisse]

Re: tree

"Bill Cunningham" <nospam@nspam.i nvalidwrites:

pgs 140-1 of kandr2 talk about recursion. I tried typing in the code
char by char and couldn't find the bugs so I just read the code and a new
concept to me jumped out. Maybe this is what it means by recursion.

There is no connection between recursion and the question you ask. I
know that this is unhelpful as an answer if you think you have seen a
connection, but then the only way forward would be for you to explain
what you see as the connection.

struct tnode *addtree (struct tnode *, char *);
>
is declared on p 140. But I noticed this on p 141.
>
struct tnode *addtree (struct tnode *p, char *w);
>
Can someone explain to me why the parameters are changing here?

These differences have no effect whatsoever. In a function
declaration (note declaration, not in a function definition) you are
free to omit the names of the parameters[1]. If you name them, the
names carry no force other than as information to the (human) reader.

If you repeat the declaration more than once, you can use different or
omit some or all of them at will for no effect at all. When you come
to define the function you must use names but they don't have to match
any that you might have used before in any declarations of the
function.

Would they
need to change more with the program on pages 140-1 ?

I can't understand this question. If you don't include code with a
question you limit yourself to answers from people who have the exact
edition of the book you are talking about.

[1] There is special case where one parameter is the dimension of
another that is a VLA, but lets put that to one side for the moment.

--
Ben.

[Bartc]

Re: tree


"Bill Cunningham" <nospam@nspam.i nvalidwrote in message
news:491e1991$0 $5486$bbae4d71@ news.suddenlink .net...

pgs 140-1 of kandr2 talk about recursion. I tried typing in the code
char by char and couldn't find the bugs so I just read the code and a new
concept to me jumped out. Maybe this is what it means by recursion.
>
struct tnode *addtree (struct tnode *, char *);
>
is declared on p 140. But I noticed this on p 141.
>
struct tnode *addtree (struct tnode *p, char *w);

That should be "{" at the end not ";". That makes it a definition rather
than a forward declaration.

--
Bartc

[Keith Thompson]

Re: tree

"Bill Cunningham" <nospam@nspam.i nvalidwrites:

pgs 140-1 of kandr2 talk about recursion. I tried typing in the code
char by char and couldn't find the bugs so I just read the code and a new
concept to me jumped out. Maybe this is what it means by recursion.
>
struct tnode *addtree (struct tnode *, char *);
>
is declared on p 140. But I noticed this on p 141.
>
struct tnode *addtree (struct tnode *p, char *w);
>
Can someone explain to me why the parameters are changing here? Would they
need to change more with the program on pages 140-1 ?

In a function declaration that's not part of a function definition,
parameter names are optional. For each parameter, you can specify
either just the type (as in the first example), or the type and the
name (as in the second example).

In a function *definition*, on the other hand, you have to specify the
name, because that's how the body of the function knows how to refer
to the parameters.

A simple example:

int add_one(int); /* this is a legal declaration */

int add_one(int i); /* this is also a legal declaration */

int add_one(int i) /* this is a definition; the name "i" is needed */
{
return i + 1;
}

My advice to you is always to include the parameter names in function
declarations, even though they're not required. Things tend to be
less confusing if the names are always there.

This has absolutely nothing to do with recursion, and I'm at a loss to
understand why you would think that it does. I think you saw the word
"recursion" on a page, saw these two declarations nearby, didn't
understand the declarations, and took a wild guess that they must have
something to do with recursion. These wild guesses of yours are
making learning far more difficult than it needs to be. I have
mentioned this to you several times in the past; it obviously hasn't
done any good.

Recursion means a function calling itself. I'm sure that K&R2
explains it better than I could.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Bill Cunningham]

Re: tree


"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
news:877i75kc5g .fsf@bsb.me.uk. ..

I can't understand this question. If you don't include code with a
question you limit yourself to answers from people who have the exact
edition of the book you are talking about.
>
[1] There is special case where one parameter is the dimension of
another that is a VLA, but lets put that to one side for the moment.

A declaration of say int func (int *, int *);
later change in the program to
int func (int *i, int *i);
later on, and then to something else later or would the body of the function
need to change?

Bill

[Bill Cunningham]

Re: tree


"Keith Thompson" <kst-u@mib.orgwrote in message
news:lnwsf568lu .fsf@nuthaus.mi b.org...

Recursion means a function calling itself. I'm sure that K&R2
explains it better than I could.

I'm not quite sure of what it is yet. With a struct is it like this ?

struct node {
int i;
char c;
struct node one;
struct node two;
};

I am so glad there is a C community to go to with these questions and
kandr2. It seems like right now I'm learning more but it's so fuzzy that it
might *settle wrong* or in other words I might learn it wrong.

I think I can take the trees on p 140-1 and § 6.5 and write a tree
program. I tried coping word from word and got too many bugs.

Bill

[Barry Schwarz]

Re: tree

On Fri, 14 Nov 2008 19:36:27 -0500, "Bill Cunningham"
<nospam@nspam.i nvalidwrote:

pgs 140-1 of kandr2 talk about recursion. I tried typing in the code
>char by char and couldn't find the bugs so I just read the code and a new
>concept to me jumped out. Maybe this is what it means by recursion.

The recursion talked about on page 140 is a "recursive declaration"
which they further describe as struct tnode containing a pointer to an
instance of a struct tnode. They then go on to call this a
"self-referential structure" which is a better term since the struct
does not actually contain itself but only a pointer (reference) to
itself.

The recursion talked about on page 141 is the function addtree calling
itself. This is what is usually meant when talking about recursion.

>
struct tnode *addtree (struct tnode *, char *);
>
>is declared on p 140. But I noticed this on p 141.
>
>struct tnode *addtree (struct tnode *p, char *w);

NO, you did not notice this on page 141. The line of code in question
on page 141 is the start of the function definition and does not
contain any semicolons.

>
>Can someone explain to me why the parameters are changing here? Would they
>need to change more with the program on pages 140-1 ?

The parameters didn't change at all. The first is a pointer to struct
and second is a pointer to char. The difference in the code is that
for the function definition the parameters must have names while in
the prototype they are optional and usually omitted.

--
Remove del for email

[Joachim Schmitz]

Re: tree

Bill Cunningham wrote:

"Keith Thompson" <kst-u@mib.orgwrote in message
news:lnwsf568lu .fsf@nuthaus.mi b.org...
>

>Recursion means a function calling itself. I'm sure that K&R2
>explains it better than I could.

>
I'm not quite sure of what it is yet. With a struct is it like
this ?
struct node {
int i;
char c;
struct node one;
struct node two;
};

No, that's nor a function calling itself, it is a struct containing itself
and as such illegal/impossible.

What you can do is:

struct node {
int i;
char c;
struct node *one;
struct node *two;
};

i.e. have pointers to the struct inside the struct.
But still this hasn't got anything to do woth recursive functions.

Bye, Jojo

[Ben Bacarisse]

Re: tree

"Bill Cunningham" <nospam@nspam.i nvalidwrites:

"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
news:877i75kc5g .fsf@bsb.me.uk. ..
>

>I can't understand this question. If you don't include code with a
>question you limit yourself to answers from people who have the exact
>edition of the book you are talking about.
>>
>[1] There is special case where one parameter is the dimension of
>another that is a VLA, but lets put that to one side for the
>moment.

These bits you quote don't seem to have anything to with the question
you go one to ask.

A declaration of say int func (int *, int *);
later change in the program to
int func (int *i, int *i);
later on, and then to something else later or would the body of the function
need to change?

I think the answer is no but the question is a bit fuzzy. The names
used in the declaration of a function have no effect on the body of
the function.

--
Ben.

[Bill Cunningham]

Re: tree


"Joachim Schmitz" <nospam.jojo@sc hmitz-digital.dewrote in message
news:gfm931$mg$ 1@online.de...

What you can do is:
>
struct node {
int i;
char c;
struct node *one;
struct node *two;
};
>
i.e. have pointers to the struct inside the struct.
But still this hasn't got anything to do woth recursive functions.

So basically what your saying is that recursion in C involves pointer ?
Right?

Bill

[osmium]

Re: tree

"Bill Cunningham" wrote:

"Joachim Schmitz" <nospam.jojo@sc hmitz-digital.dewrote in message
news:gfm931$mg$ 1@online.de...
>

>What you can do is:
>>
>struct node {
> int i;
> char c;
> struct node *one;
> struct node *two;
>};
>>
>i.e. have pointers to the struct inside the struct.
>But still this hasn't got anything to do woth recursive functions.

>
So basically what your saying is that recursion in C involves pointer ?
Right?

No! He didn't say that and he didn't imply that. All he did was (partially)
correct your sloppy copy job which resulted in non-acceptable code.

Pointers and recursion are two separate issues. Choose one to focus on and
then focus. I suggest you focus on pointers first.

BTW, how is that search for a wordier book as an alternative to K&R coming?

[Ben Bacarisse]

Re: tree

"Bill Cunningham" <nospam@nspam.i nvalidwrites:

"Joachim Schmitz" <nospam.jojo@sc hmitz-digital.dewrote in message
news:gfm931$mg$ 1@online.de...
>

>What you can do is:
>>
>struct node {
> int i;
> char c;
> struct node *one;
> struct node *two;
>};
>>
>i.e. have pointers to the struct inside the struct.
>But still this hasn't got anything to do woth recursive functions.

>
So basically what your saying is that recursion in C involves pointer ?
Right?

There is an important distinction between recursive functions (those
that contains calls to themselves) and recursive structures.
Recursive structures always need pointers, but recursive function
don't.

In my opinion, Joachim Schmitz, went a little too far by saying "this
hasn't got anything to do with recursive functions". He was, no
doubt, keen to avoid confusing you and equally keen to keep the
distinction between recursive functions and self-referential
structures (another name for structs like node) as clear as possible
but every time you see a struct that includes a pointer to one or more
instances of the same struct, there will probably be simple recursive
algorithms to manipulate that data structure. This is because there
is a string connection between the two disrtinct ideas of recursive
functions and self-referential structures.

For example, if you have a linked-list:

struct lnode { int num; struct lnode *next };

then you can find the sum of the numbers in such a list recursively
like this:

int sum_list(struct lnode *list)
{
return list == NULL ? 0 : list->num + sum_list(list->next);
}

The pay-off is even greater when dealing with trees where there are at
least two "nested" pointers. For example if we have a tree containing
numbers:

struct node {
int num;
struct node *left;
struct node *right;
};

we can write a function to add up all the numbers very simply:

int sum_tree(struct node *tree)
{
return tree == NULL ? 0 :
tree->num + sum_tree(tree->left) + sum_tree(tree->right);
}

--
Ben.

[Joachim Schmitz]

Re: tree

Bill Cunningham wrote:

"Joachim Schmitz" <nospam.jojo@sc hmitz-digital.dewrote in message
news:gfm931$mg$ 1@online.de...
>

>What you can do is:
>>
>struct node {
> int i;
> char c;
> struct node *one;
> struct node *two;
>};
>>
>i.e. have pointers to the struct inside the struct.
>But still this hasn't got anything to do woth recursive functions.

>
So basically what your saying is that recursion in C involves
pointer ? Right?

As osmium and Ben told you meanwhile: Neither were I saying this, nor it'd
be right.

Bye, Jojo

[Joachim Schmitz]

Re: tree

Ben Bacarisse wrote:

"Bill Cunningham" <nospam@nspam.i nvalidwrites:
>

>"Joachim Schmitz" <nospam.jojo@sc hmitz-digital.dewrote in message
>news:gfm931$mg $1@online.de...
>>

>>What you can do is:
>>>
>>struct node {
>> int i;
>> char c;
>> struct node *one;
>> struct node *two;
>>};
>>>
>>i.e. have pointers to the struct inside the struct.
>>But still this hasn't got anything to do woth recursive functions.

>>
> So basically what your saying is that recursion in C involves
>pointer ? Right?

>
There is an important distinction between recursive functions (those
that contains calls to themselves) and recursive structures.
Recursive structures always need pointers, but recursive function
don't.
>
In my opinion, Joachim Schmitz, went a little too far by saying "this
hasn't got anything to do with recursive functions". He was, no
doubt, keen to avoid confusing you and equally keen to keep the
distinction between recursive functions and self-referential
structures (another name for structs like node) as clear as possible

Yes, exactly

but every time you see a struct that includes a pointer to one or more
instances of the same struct, there will probably be simple recursive
algorithms to manipulate that data structure. This is because there
is a string connection between the two disrtinct ideas of recursive
functions and self-referential structures.

To be perfectly honest: I didn't think of that connection between those two
concepts, but of course you're right, there is a strong connection between
the two.

For example, if you have a linked-list:
>
struct lnode { int num; struct lnode *next };
>
then you can find the sum of the numbers in such a list recursively
like this:
>
int sum_list(struct lnode *list)
{
return list == NULL ? 0 : list->num + sum_list(list->next);
}

compared to the much wordier iterative version:

int sum_list(struct lnode *list)
{
int sum = 0;
struct lnode *curr = list;

while ( curr != NULL ) {
sum += curr->num;
curr = list->next;
}
return sum;
}

( I hope I didn't screw it up too badly)

Bye, Jojo