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]

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.

 

[Bartc]

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.

 

[Keith Thompson]

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.

 

[Bill Cunningham]

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]

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]

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.

 

[Joachim Schmitz]

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]

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.

 

[Bill Cunningham]

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]

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]

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);
}

 

[Joachim Schmitz]

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]

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