2
\$\begingroup\$

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)
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Bex Sep 4 '17 at 9:50
  • \$\begingroup\$ 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? \$\endgroup\$ – 200_success Sep 4 '17 at 14:08
  • \$\begingroup\$ the return statement is mandatory, otherwise it will be like looping infinitely. @Bex \$\endgroup\$ – Billal Begueradj Sep 4 '17 at 19:38
  • 3
    \$\begingroup\$ The return statement is vital. The return value is nonsensical. \$\endgroup\$ – Bex Sep 5 '17 at 5:12
  • 1
    \$\begingroup\$ Come to think of it - does this code work? \$\endgroup\$ – Bex Sep 7 '17 at 7:46
8
\$\begingroup\$

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)
\$\endgroup\$
  • 3
    \$\begingroup\$ +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. \$\endgroup\$ – ymbirtt Sep 4 '17 at 10:12
  • \$\begingroup\$ @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 (?). \$\endgroup\$ – Pierre.Sassoulas Sep 4 '17 at 11:55
11
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Should the last example read length /= 2 not length =/ 2? \$\endgroup\$ – Charlie Harding Sep 4 '17 at 10:53
  • 1
    \$\begingroup\$ Also - missing a colon in that same function. \$\endgroup\$ – wizzwizz4 Sep 4 '17 at 12:55
  • 1
    \$\begingroup\$ This is a great code review community! Thank you. Corrected as per your observations \$\endgroup\$ – Bex Sep 4 '17 at 13:16
  • \$\begingroup\$ I don't get what you mean by 1/2 == 0 and onwards. Can you explain? \$\endgroup\$ – Daniel Sep 4 '17 at 14:50
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – 409_Conflict Sep 4 '17 at 14:57
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ – kafka Sep 4 '17 at 12:20
  • 1
    \$\begingroup\$ Can you elaborate on "do not use the parameters inside your function"? \$\endgroup\$ – Gerardo Furtado Sep 4 '17 at 13:23
  • \$\begingroup\$ @BillalBEGUERADJ thanks will have a read (I didn't downvote btw...) \$\endgroup\$ – kafka Sep 4 '17 at 19:21
  • 1
    \$\begingroup\$ -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) \$\endgroup\$ – insert_name_here Sep 4 '17 at 22:15
  • \$\begingroup\$ @BillalBEGUERADJ Thank you, reading it right now. Also, as kafka, I didn't downvote you: my question was a genuine curiosity. \$\endgroup\$ – Gerardo Furtado Sep 5 '17 at 3:05
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Will that return False statement ever be reached? \$\endgroup\$ – Bex Sep 4 '17 at 10:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Mike Dimmick Sep 4 '17 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.