recursively removing from a linked list

Question

I'm trying to convert a removal method from an ordered linked list into a recursive form and am having trouble doing so. I'm trying to convert the code in remove_recursive into recursive form and thought I just needed to change the while statement to an if and to call the function at the end but this isn't working

def remove(self, item):
    curr = self.__head
    prev = None
    self.remove_recursive(item, curr, prev)

def remove_recursive(self, item, curr, prev):
    while curr != None and curr.get_data() != item:
        prev = curr
        curr = curr.get_next()
    if prev == None:
        self.__head = curr.get_next()
    else:
        prev.set_next(curr.get_next())
    self.__count -= 1

I tried

def remove_recursive(self, item, curr, prev):
    if curr != None and curr.get_data() != item:
        prev = curr
        curr = curr.get_next()
        return self.remove_recursive(item, curr, prev)
    if prev == None:
        self.__head = curr.get_next()
    else:
        prev.set_next(curr.get_next())
    self.__count -= 1

" thought I just needed to change the while statement to an if and to call the function at the end but this isn't working" - what isn't working? you didn't show us what you tried. — Nir Alfasi, Oct 27 '17 at 00:24
You need the recursive function to return a pointer to the head of the list after it returns. I'll give you a hint. The first call from `remove` to `remove_recursive` should be `self__.head = remove_recursive(self__.head, item)` — MFisherKDX, Oct 27 '17 at 00:24
@MFisherKDX just updated it to what I tried before and it seems to work this time, maybe I did something different, thanks for the help anyway! — , Oct 27 '17 at 00:35
@BadUserName -- if you don't mind the nitpicky gauntlet, you could post your code as an answer to your question and see what happens. — MFisherKDX, Oct 27 '17 at 00:47

score 2 · Answer 1 · answered Oct 27 '17 at 16:46

To delete a node N from a linked list, one must make the previous node's next pointer skip over N by pointing to N's next node in the sequence. For instance, if we have the following list and we want to delete item 1 we actually need to set the value of 0's next pointer to 1's next pointer.

head
 V
 0 --> 1 --> 2 -->(None)
 ^     ^     ^ 
prev  cur   next

The traditional iterative solution is to use a while loop to iterate over the list keeping track of both the prev and cur pointers. The OPs posted answer does exactly this but instead uses a recursive call in place of a while loop.

If instead we used the recursive stack to keep track of the pointers as we iterate, stack frame i's current pointer is stack frame i+1's previous pointer. If we define remove_recursive(current, data) to be a function that returns a pointer to the list or sublist pointed to by current after removing the first instance of data from the list, then we can perform the pointer updates as we "fall off the stack."

Our recursive definition looks like this:

Base cases:

1) Removing an item from an empty list
Can't do it. Return the empty list (None)

2) Remove the item from the front of the list
The sub-list with the first item removed is simply the sub-list pointed to by the next pointer. Return the next pointer. (If duplicate items are allowed and you want to delete all duplicate items, then continue recurse here -- see next step)

Recursive case:
Delete the item from the sublist pointed to by the next pointer. This is the definition of remove_recursive with current.next passed to it. Set current.next to the return value of remove_recursive(current.next, data) and return current.

Here is my code -- which is the recursive solution in the more traditional form

def remove_recursive(self, cur, data):
    if cur == None:
        return None
    elif cur.get_data() == data:
        return cur.get_next() # removes only the first instance of data
    else:
        cur.set_next(self.remove_recursive(cur.get_next(), data))
        return cur

def remove(self, data):
    self.__head = self.remove_recursive(self.__head, data)

An observation. This recursive method uses O(N) memory in worst case as it uses the stack to store all the previous pointers. The iterative while loop method only uses O(1) extra memory because it only needs to keep track of one previous pointer. The OPs answer is actually tail recursive and in theory would have O(1) memory -- except as I understand it, python does not optimize for tail recursion.

score 0 · Answer 2 · answered Oct 27 '17 at 01:02

0

This is the solution I have found to the problem

def remove_recursive(self, item, curr, prev):
    if curr != None and curr.get_data() != item:
        prev = curr
        curr = curr.get_next()
        return self.remove_recursive(item, curr, prev)
    if prev == None:
        self.__head = curr.get_next()
    else:
        prev.set_next(curr.get_next())
    self.__count -= 1

answered Oct 27 '17 at 01:02

I'm going to up-vote this because it works. You swapped the while loop in the iterative method for recursion. Notice you have to keep track of the previous pointer. You can do this more elegantly by making the recursive stack hold the previous pointer, and I'll post an alternate recursive solution most people are familiar with shortly. – MFisherKDX Oct 27 '17 at 15:52

recursively removing from a linked list

2 Answers2