Recursion of Linked List

Question

When given an array of integers, I'm trying to change each element with the product of the integers before it.

For example, int[] array = {2,2,3,4}; is now: {2, 4, 12, 48};

I added each element to a LinkedList, and I'm trying to do this recursively.

This is what I have:

Node curr = list.getFirst();
product(curr);

public static void product(Node curr)
{
    if(curr == null)
    {
        return;
    }
    else
    {
        int data = curr.getData() * curr.getNext().getData();
        Node newNode = new Node(data);
        curr.setNext(newNode);

        //  product(curr);
    }
}

The first product works: {2,4}, but when I try to put in the recursion, I get a stackoverflow. Any suggestions??

Edit: So the reason that I'm either getting a stackoverflow or null pointer exception is because I'm updating the list, and then trying to get the next integer(but since there's only two elements in the list, there isn't a getNext()). I'm not sure how to fix this.

Part of the problem would seem to be that your adding a next node, so everytime you recurse there is a next node, hence no end to the recursion. Not sure why Tims solution didnt fix that though. — D. Ben Knoble
– D. Ben Knoble, Commented Jun 23, 2015 at 2:06
@BenKnoble I accidentally left in one line from his old program in my original post, though I have since removed it. Maybe he ran this older version of the code. — Tim Biegeleisen
– Tim Biegeleisen, Commented Jun 23, 2015 at 2:07

Tim Biegeleisen · Accepted Answer · 2015-06-23 01:47:06Z

1

It looks like you were getting a bit tied up in the recursion. I modified your method to accept a Node along with the product from the previous iteration. At each step of the iteration I update the value in the already-existing List, so there is no need for using the new operator.

public static void product(Node curr, int value) {
    if (curr == null) {
        return;
    }
    else {
        int data = value * curr.getData();  // compute current product
        curr.setData(data);                 // update Node
        product(curr.getNext(), data);      // make recursive call
    }
}

edited Jun 23, 2015 at 1:47

answered Jun 23, 2015 at 1:43

Tim Biegeleisen

526k32 gold badges324 silver badges399 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

almightyGOSU Over a year ago

Where are you getting newNode from?

Tim Biegeleisen Over a year ago

Sorry I am on a mobile device and I forgot to delete his old code.

kris Over a year ago

Thanks Tim! Although I'm still getting a stack overflow with this code.

Tim Biegeleisen Over a year ago

Can you elaborate on the error? The code should work with no issues.

kris Over a year ago

I wanted to do it with the setData method, but your way worked!

|

sam_haz · Accepted Answer · 2015-06-23 02:20:21Z

There are actually two issues with the code.

The recursion never ends, i.e. it is not actually moving to a smaller "subproblem" as the recursion is calling the same node again and again.

After creating a new node and modifying the next we also need to connect the node "after" the next node otherwise the link will be lost. Please check the below method which addresses both the issues.

Although I didn't do an excessive testing it is working for simple dataset. Original List: 2->4->5->6->8->null Multiplied List: 2->8->40->240->1920->null

public void product(Node curr) {
    if (curr.getNext() == null) {
        return;
    } else {
        int data = curr.getData() * curr.getNext().getData();
        Node newNode = new Node();
        newNode.setData(data);
        Node nodeAfterNextNode = curr.getNext().getNext();
        newNode.setNext(nodeAfterNextNode);
        curr.setNext(newNode);

        product(newNode);
    }
}

Tony Vu · Accepted Answer · 2015-06-23 03:29:46Z

0

It is because you call recursive method on the current node, so it is actually never move forward in the LinkedList. You can simply update the next node's data and call the recursive method on it. See the code below:

Node curr = list.getFirst();
product(curr);

public static void product(Node curr)
{
    Node next  = curr.getNext();   
    if(next == null)
    {
        return;
    }
    else
    {
        int data = curr.getData() * next.getData();
        next.setData(data);
        product(next);
    }
}

edited Jun 23, 2015 at 3:29

answered Jun 23, 2015 at 1:47

Tony Vu

4,3813 gold badges35 silver badges42 bronze badges

2 Comments

kris Over a year ago

Unfortunately this gives me a null pointer exception, I think because we don't know if curr has a getNext, this may be why my original code didnt work eithe r

Tony Vu Over a year ago

Yes, you are right, next can be null so we should return when next is null. Please see updated code.

Collectives™ on Stack Overflow

Recursion of Linked List

3 Answers 3

7 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related