5
\$\begingroup\$

I have written this piece of code that implements the double factorial in Python both iteratively and recursively; the code works without problems, but I'm interested in improving my overall programming style. Here's the code:

def semif_r(n):                 #recursive implementation
    if n == 0 or n == 1:
        z = 1
    else:
        z= n * semif_r(n-2)
    return z


def semif_i(n):             #iterative implementation
    N = 1
    if n == 0 or n == 1:
        return 1
    elif n%2 == 1:
        for i in range(0,n/2):
            N =  (2*i + 1)*N
            VAL = N
        return n*VAL

    elif n%2 == 0:
        for i in range(0,n/2):
            N =  (2*i+2)*N
            VAL = N
    return VAL

I hope that some experienced programmers can give me some feedback about improving my code!

\$\endgroup\$
  • \$\begingroup\$ On my machine the recursive code works 'without problems' until n = 1998, at which point I get: RuntimeError: maximum recursion depth exceeded \$\endgroup\$ – Peter Wood Nov 21 '15 at 21:22
  • \$\begingroup\$ Yep, importing the sys package and changing the maximum recursions will solve this \$\endgroup\$ – james42 Nov 21 '15 at 21:31
  • \$\begingroup\$ It won't solve it, but you could mitigate problems up to a point. There is still a maximum limit. What I'm saying is the two implementations have different behaviour in the face of limited resources. You might want to create a ValueError, and document it in the function's docstring. \$\endgroup\$ – Peter Wood Nov 21 '15 at 21:56
4
\$\begingroup\$

The recursive solution

The z local variable, you can just return directly.

The else could be dropped, as the if before it returns from the function.

Adding some doctests would be useful.

def semif_r(n):
    """
    >>> semif_r(5)
    15
    >>> semif_r(6)
    48
    >>> semif_r(25)
    7905853580625
    """
    if n == 0 or n == 1:
        return 1
    return n * semif_r(n - 2)

The iterative solution

No need to declare N up front. You could declare and initialize when you need it.

VAL is unnecessary, whenever its value is referenced, it's equal to N, so you could use N instead of VAL everywhere.

The start value of a range is 0 by default, so you don't need to specify that explicitly.

In n / 2, you're counting on that integer division will occur with truncation. In Python 3 there is a separate operator // for this. It's good to make your code ready for Python 3, by using //, and adding this import:

from __future__ import division

The logic in the two range loops are almost the same. It would be good to extract that logic to a helper function.

As with the recursive implementation, doctests would be nice.


Note that in this code:

elif n%2 == 1:
    # ...

elif n%2 == 0:
    # ...

There, the 2nd elif could be replaced with a simple else, since if n % 2 != 1, then it must be inevitably 0.


Putting it all together:

def semif_i(n):  
    """
    >>> semif_i(5)
    15
    >>> semif_i(6)
    48
    >>> semif_i(25)
    7905853580625
    """
    if n == 0 or n == 1:
        return 1

    def multiply(coef):
        val = 1
        for i in range(n // 2):
            val *= (2 * i + coef)
        return val

    if n % 2 == 1:
        return n * multiply(1)

    return multiply(2)

Coding style

Please follow PEP8, the coding style guide (see the writing style in my sample implementations).

\$\endgroup\$
4
\$\begingroup\$

Simplify Simplify Simplify

janos covered the recursive case well enough, but the iterative case can be greatly reduced by simply using the same approach as your recursive algorithm. What I mean is, your recursive implementation performs N * (N-2) * (N-4) * ..., but your iterative implementation involves looping in the other direction, and then performing some extra math to boot. Rather than iterating up to N // 2, simply count by twos from the top down. range(N, 1, -2) will give you everything you want:

>>> range(1, 1, -2)
[]
>>> range(2, 1, -2)
[2]
>>> range(15, 1, -2)
[15, 13, 11, 9, 7, 5, 3]

So you could simply write your loop around that (remembering the caveat that range returns a full list, whereas xrange gives you the elements on demand):

def semif_i(n): 
    product = 1
    for i in xrange(n, 1, -2):
        product *= i
    return product

This can be reduced further using reduce(), but YMMV on whether or not this is any better:

def semif_i(n):
    return reduce(operator.mul,
        xrange(n, 1, -2),
        1)

Either way, I prefer this approach since you don't actually need a special case for n=0 or n=1. xrange() implicitly takes care of this for you by simply providing an empty range!

\$\endgroup\$

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.