# Determining if a palindrome exists in a linked list using recursion

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
if length == 0:  # even number of nodes
if length == 0 or length == 1:
return True


• I think you may go about this the wrong way. The return value carries no meaning here (since it's always True). Could you use your return value (and therefore the stack) to convey some part of your program data? If so, this construction would probably collapse to just a few lines. – Bex Sep 4 '17 at 9:50
• If-else optimization is a very common request on Code Review, and is therefore not appropriate as a question title. The site standard is for the title to state the task accomplished by the code. See How to Ask. Furthermore, please provide sufficient context for the code. What do the parameters represent? Could you provide an example usage? – 200_success Sep 4 '17 at 14:08
• the return statement is mandatory, otherwise it will be like looping infinitely. @Bex – Billal Begueradj Sep 4 '17 at 19:38
• The return statement is vital. The return value is nonsensical. – Bex Sep 5 '17 at 5:12
• Come to think of it - does this code work? – Bex Sep 7 '17 at 7:46

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.

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



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

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



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

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


• +1, specifically for repeating yourself. Whilst DRY is super-important, like all "programming commandments", it's just a guideline. Violating it here has, IMHO, actually increased code clarity. – ymbirtt Sep 4 '17 at 10:12
• @ymbirtt Good point but Imho the choice was between repeating "if length == 1" and "if length == 0" (20+ char) vs repeating "return True" (10+ char). So the example with "return True" duplicated is actually DRYer (?). – Pierre.Sassoulas Sep 4 '17 at 11:55

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
elif length == 0:  # even number of nodes



or, on one line

def recurse(head, length):


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:



or, on one line:

def recurse(head, length):


Of course, this might be better not to recurse:

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


• Should the last example read length /= 2 not length =/ 2? – Charlie Harding Sep 4 '17 at 10:53
• Also - missing a colon in that same function. – wizzwizz4 Sep 4 '17 at 12:55
• This is a great code review community! Thank you. Corrected as per your observations – Bex Sep 4 '17 at 13:16
• I don't get what you mean by 1/2 == 0 and onwards. Can you explain? – Daniel Sep 4 '17 at 14:50
• @Coal_ Using integral division (Python 2, but OP is expecting integers at the end of its recursive call, so this might be Python 2), when you divide 1 by 2, the result is 0. @Bex Maybe using while not (length < 1): will make it Python 3 compatible too. – Mathias Ettinger Sep 4 '17 at 14:57

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
if length == 0:  # even number of nodes
return True



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
elif length == 0:  # even number of nodes
return True



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.

### 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):
length /= 2


### 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):
while (length > 0):
length /= 2


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:


and our function becomes:

def pick_a_better_function_name(length):
while (length > 0):
length /= 2


### 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
while (l > 0):
l /= 2


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.

• Is your point on 'do not use function params directly, no matter what language' (paraphrased) definitely correct? I'm not doubting you, just haven't seen this before with Python... – kafka Sep 4 '17 at 12:20
• Can you elaborate on "do not use the parameters inside your function"? – Gerardo Furtado Sep 4 '17 at 13:23
• @BillalBEGUERADJ thanks will have a read (I didn't downvote btw...) – kafka Sep 4 '17 at 19:21
• -1; making your own class just so you can get rid of a function's parameters is just plain silly. I don't see any reason to do this, and it makes the function much harder to use if it's imported... you need to do mymodule.MyGlobalVariables.head = head; newhead = mymodule.better_function_name(length) instead of just newhead = mymodule.better_function_name(head, length) – insert_name_here Sep 4 '17 at 22:15
• @BillalBEGUERADJ Thank you, reading it right now. Also, as kafka, I didn't downvote you: my question was a genuine curiosity. – Gerardo Furtado Sep 5 '17 at 3:05

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
elif length == 0:  # even number of nodes
else:
return False
return True

• Will that return False statement ever be reached? – Bex Sep 4 '17 at 10:14
• Yes, of course - it will be reached on every stack frame when the recursive call to recurse returns, unless an exception occurs (perhaps length is far greater than the actual chain of next pointers, leading to a null pointer dereference). This does subtly change the behaviour of the function, which is to return None when the initial list is two or more items in length (this is Python's standard behaviour if no return statement is found). As originally written, recurse would return True if the original list was either zero or one item in size, or None if it had to search. – Mike Dimmick Sep 4 '17 at 10:35