Determining if a palindrome exists in a linked list using recursion

Question

Summary of code:

This code recurses through half of the LinkedList, "adding" the left half node's to the call stack. Then, once at the middle, the code returns the first node of the right side (or more accurately, it assigns it to a variable, "right_node"). As the call stack collapses, the code compares the left nodes with the right nodes, and the right node is assigned to right node's next node.

The full code and updates are available here.

Specific questions:

I have a recursive function with two base cases, and both involve returning True, but each have to do a different step beforehand. Is there a better way to write out this if else statement structure?

This is the code snippet that features the if/else structure:

def recurse(head, length, node):
    if length == 1:  # odd number of nodes
        node[0] = head.next
    if length == 0:  # even number of nodes
        node[0] = head
    if length == 0 or length == 1:
        return True

    recurse(head.next, length/2, node)

Answer 1

Since the first two statements are mutually exclusive, you can write it as:

if <statement>:
    <action>
elif <statement>:
    <action>
if <statement>:
    <action>

... optionally adding an else clause at the end.
Your code then becomes:

def recurse(head, length, node):
    if length == 1:  # odd number of nodes
        node[0] = head.next
    elif length == 0:  # even number of nodes
        node[0] = head
    if length == 0 or length == 1:
        return True

    recurse(head.next, length/2, node)

You can shorten the last if-statement by using the in keyword:

def recurse(head, length, node):
    if length == 1:  # odd number of nodes
        node[0] = head.next
    elif length == 0:  # even number of nodes
        node[0] = head
    if length in (0, 1):
        return True

    recurse(head.next, length/2, node)

You may want to get rid of the second if altogether:

def recurse(head, length, node):
    if length == 1:  # odd number of nodes
        node[0] = head.next
        return True
    elif length == 0:  # even number of nodes
        node[0] = head
        return True

    recurse(head.next, length/2, node)

Answer 2

Generally, when you end up with an expression like this, it is a sign that something is not right, and something needs rethinking or refactoring.

I don't see the point of node here - since you always write to node[0] - and if you would eliminate it, that is, use it as the return value, your function would be a lot simpler:

def recurse(head, length):
    if length == 1:  # odd number of nodes
        return head.next
    elif length == 0:  # even number of nodes
        return head

    return recurse(head.next, length//2)

or, on one line

def recurse(head, length):
    return head if length==0 else head.next if length==1 else recurse(head.next, length//2)

BUT - 1//2 == 0, so both of these get a lot easier if you realize you have only one base case:

def recurse(head, length):
    if length == 0:
        return head

    return recurse(head.next, length//2)

or, on one line:

def recurse(head, length):
    return head if length==0 else recurse(head.next, length//2)

Of course, this might be better not to recurse:

def nonrecurse(head, length):
    while (length > 0): 
        head = head.next
        length//=2

    return head

Answer 3

In general:

You could nest the "If A" and "If B" statements in the "If A or B" statement:

def recurse(head, length, node):
    if length == 0 or length == 1:
        if length == 1:  # odd number of nodes
            node[0] = head.next
        if length == 0:  # even number of nodes
            node[0] = head
        return True

    recurse(head.next, length/2, node)

Additionally, as mentioned in Coal_'s answer, you can change the second nested if to an elif in this case:

def recurse(head, length, node):
    if length == 0 or length == 1:
        if length == 1:  # odd number of nodes
            node[0] = head.next
        elif length == 0:  # even number of nodes
            node[0] = head
        return True

    recurse(head.next, length/2, node)

You can, of course, add an else block after the if A or B block, if it's needed.

---

In this specific case, your function can be greatly simplified; see Bex's answer.

Answer 4

Choose the right name

I was scared when I read the name of your function recurse() because recently I have been cursed, and that function's name threatens to re-curse me. That is why you must choose the name that says why your function actually does.

No empty lines before return

I see frequently Python code on this website where the authors leave an empty line before the return statement. I do not see the mystery behind this practice on PEP8.

Natural way to be recursive

The natural way to design a recursive function is to write the exit condition first, not at the end. So you could re-write your function like this:

def recurse(head, length, node):
    if length in {0, 1} return True # write the exit condition first
    # write the rest of code here

Never hire a developer who computes the factorial using Recursion

In software engineering, we have this saying "Never hire a developer who computes the factorial using Recursion". That is why I do not want to suggest an improved recursive version of your function. Bex' answer mentioned this by the end, but I am just emphasizing it:

def better_function_name(head, length):
    while (length > 0): 
        head = head.next
        length /= 2    
    return head

Too much parameters

Parameters belong to a level of abstraction which is different from that of the function they are passed to. That is why we must use as less parameters as possible with functions (and classes initializers). That is why I want to render your function monadic.

Bex explained you why you do not really need the node parameter. So we let us see if we can get rid of length and head parameters.

I think by head (and node), you refer to a data structure you are using in other places of your program. The most obvious way to do fulfill this goal is by using declaring it global:

def pick_a_better_function_name(length):
    global head
    while (length > 0): 
        head = head.next
        length /= 2    
    return head

But it is commonly advised not to use global variables whatever the programming language you are coding with because they can result into, among other ugly things, spaghetti code. An alternative to use a monadic (one parameter) function and avoid global is to use a class where you store all your global variables:

Class MyGlobalVariables:
    head = ...

and our function becomes:

def pick_a_better_function_name(length):
    head = MyGlobalVariables.head
    while (length > 0): 
        head = head.next
        length /= 2    
    return head

Do not use function's parameters directly

Whatever the programming language you use, do not use the parameters inside your function:

def my_function(param):
   par = param
   # Now work with "par" instead of "param"

So the improved approach of your function would be:

def pick_a_better_function_name(length):
    l = length
    head = MyGlobalVariables.head
    while (l > 0): 
        head = head.next
        l /= 2    
    return head

EDIT:

The fact the question is closed does not encourage me to elaborate more about what the commentators pointed on. However, that is something you can read on Do not make a direct use of function parameters.

Answer 5

To complement Coal_'s answer and assuming your function returns False when length is neither 1 nor 0:

def recurse(head, length, node):
    if length == 1:  # odd number of nodes
        node[0] = head.next
    elif length == 0:  # even number of nodes
        node[0] = head
    else:
        recurse(head.next, length/2, node)
        return False
    return True