Simple Recursion

[craig delehanty]

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(Ln ode *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

[Karl Heinz Buchegger]

Re: Simple Recursion



craig delehanty wrote:[color=blue]
>[/color]
[color=blue]
> void List::addOne(Ln ode *t)
> {
> if(t->next == NULL)
> t->val += 1;[/color]

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
[color=blue]
> Once the pointer t->next == NULL should not the function add 1 to each
> node as it reverses out of the list?[/color]

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
kbuchegg@gascad .at

[Peter van Merkerk]

Re: Simple Recursion


"craig delehanty" <craigdele@e3.n et.nz> wrote in message
news:3fab7287@n ews.iconz.co.nz ...[color=blue]
> 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[/color]
list[color=blue]
> until it finds NULL. Then as it unwinds I wish it to add 1 to each[/color]
value[color=blue]
> 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(Ln ode *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?[/color]

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(Ln ode *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(Ln ode *t)
{
while(t)
{
t->val += 1;
t = t->next;
}
}

--
Peter van Merkerk
peter.van.merke rk(at)dse.nl


[color=blue]
>
> Craig
>[/color]

[Karl Heinz Buchegger]

Re: Simple Recursion



Peter van Merkerk wrote:[color=blue]
>
>
> Though I wonder why you userecursion for this.[/color]

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

--
Karl Heinz Buchegger
kbuchegg@gascad .at

[wogston]

Re: Simple Recursion

> Below is a simple recursive function.I want to advance through the list[color=blue]
> 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.[/color]

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

while ( node )
{
increase(node);
node = node->next;
}