By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,305 Members | 1,822 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,305 IT Pros & Developers. It's quick & easy.

Simple Recursion

P: n/a
I have a program that creates a linked list. I have added 3 nodes with
the following values.

head -> 4 -> 13 -> 19 -> NULL

Below is a simple recursive function.I want to advance through the list
until it finds NULL. Then as it unwinds I wish it to add 1 to each value
of each node. My problem is it only adds 1 to the 1st created node.

The function below gives me the following output

head -> 4 -> 13 -> 20 -> NULL, I want: head -> 5 -> 14 -> 20 -> NULL

void List::addOne(Lnode *t)
{
if(t->next == NULL)
t->val += 1;
else
addOne(t->next);
}

void List::addOne()
{
addOne(head);
}

Once the pointer t->next == NULL should not the function add 1 to each
node as it reverses out of the list?

Can anyone advise me of my error please?

Craig

Jul 19 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a


craig delehanty wrote:
void List::addOne(Lnode *t)
{
if(t->next == NULL)
t->val += 1;
Read it in plain english:

if and only if the value of the next field of the node where t points
to equals NULL, add 1 to t->val.

That fact that this adds 1 to the first node in your list (which clearly
has not a value of NULL for its next field) indicates for a problem in
the way you either:
* build up your list
* you output the list

What you want to do is:

void List:: addOne( Lnode* t )
{
if( t == NULL )
return;
addOne( t->next ); // recurse until the end of the list is reached

t->val += 1; // add 1 to the current node ...
} // ... and unwind the recursion one step
Once the pointer t->next == NULL should not the function add 1 to each
node as it reverses out of the list?


As you have written it now, no. 1 is added only if the t->next
equals NULL. That's what you have written and that's what the
computer does.

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 19 '05 #2

P: n/a

"craig delehanty" <cr*******@e3.net.nz> wrote in message
news:3f******@news.iconz.co.nz...
I have a program that creates a linked list. I have added 3 nodes with
the following values.

head -> 4 -> 13 -> 19 -> NULL

Below is a simple recursive function.I want to advance through the list until it finds NULL. Then as it unwinds I wish it to add 1 to each value of each node. My problem is it only adds 1 to the 1st created node.

The function below gives me the following output

head -> 4 -> 13 -> 20 -> NULL, I want: head -> 5 -> 14 -> 20 -> NULL

void List::addOne(Lnode *t)
{
if(t->next == NULL)
t->val += 1;
else
addOne(t->next);
}

void List::addOne()
{
addOne(head);
}

Once the pointer t->next == NULL should not the function add 1 to each
node as it reverses out of the list?

Can anyone advise me of my error please?
No, only the last node will be incremented because the increment will
only happen when t->next == NULL. When the last node is encountered, it
will do the increment, then it will return and nothing else will happen
because the else clause doesn't do anything after the addOne() call. If
you would have used a debugger it would be easy to see why this function
doesn't work the way you expected.

One way to fix that function is this:
void List::addOne(Lnode *t)
{
if(t->next != NULL)
{
addOne(t->next);
}
t->val += 1;
}

Though I wonder why you userecursion for this. The iterative version is
simpler, and more efficient and won't run out of stack space when the
linked list is really long.

void List::addOne(Lnode *t)
{
while(t)
{
t->val += 1;
t = t->next;
}
}

--
Peter van Merkerk
peter.van.merkerk(at)dse.nl

Craig

Jul 19 '05 #3

P: n/a


Peter van Merkerk wrote:


Though I wonder why you userecursion for this.


It could be a homework exercise to get used to
recursions.

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 19 '05 #4

P: n/a
> Below is a simple recursive function.I want to advance through the list
until it finds NULL. Then as it unwinds I wish it to add 1 to each value
of each node. My problem is it only adds 1 to the 1st created node.


I don't see why it should be recursive, do something like this:

while ( node )
{
increase(node);
node = node->next;
}
Jul 19 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.