Python Recursion

Keys to recursion:

  • base case: the “one line” operation that does the calculation
  • state maintenance: remember the calculation result
  • stop condition: logic that stops the recursion

An example to illustrate:

# calculate the sum of all integers up to n
def tail_recursive_sum(n, total=0):
    if n == 0: # the stop condition
        return total
    total += n # the base case
    return sum(n-1, total) # total is used to maintain the state

# simplified version
def sum(n, total=0):
    if n== 0: return total
    return sum(n-1, total+n)

Another way to write this function:

def recursive_sum(n):
    if n == 1:
        return 1
    return n + sum(n-1)

The main difference is that recursive_sum does not use a variable to maintain the state. It relies on the function call stack. Assuming cur = 3, the above function call looks like this:

3 + sum(3-1)
3 + 2 + sum(2-1)
3 + 2 + 1

Notice that the 1st and 2nd call cannot be completed unless the 3rd call returns 1.

The call stack looks quite different with the tail_recursive_sum approach:

sum(3-1, 0+3)
sum(2-1, 3+2)
sum(1-1, 5+1)

When there is no additional operations other than the recursive function call at the end of a function, it is called tail recursion. (Some language support tail recursion optimization but Python doesn’t)

Here are some exercise to play with:


Python list sort vs sorted

A concise answer from this SO post:

  • sorted returns a new list, list.sort() mutate the calling list and returns None
  • For lists, list.sort() is faster than sorted() because it doesn’t have to create a copy. For any other iterable, you have no choice.

Google Python Style Guide

Useful tips from Google’s python style guideline:

Use nested for-loops instead of complex list comprehensions

for x in range(10):
      for y in range(5):
          if x * y > 10:
              result.append((x, y))


result = [(x, y) for x in range(10) for y in range(5) if x * y > 10]

Use default iterators instead of iterating over a returned list

for key in adict: ...
if key not in adict: ...
if obj in alist: ...
for line in afile: ...
for k, v in adict.items(): ...


for key in adict.keys(): ... 
      if not adict.has_key(key): ...
      for line in afile.readlines(): ...
      for k, v in dict.iteritems(): ...
  • Use “implicit” false if at all possible (for sequences like strings, lists, tuples)
  • Never compare a boolean variable to False using == (because falsy does not == False)
  • Compare integers to explicit integer values rather than rely on implicit false (accidentally handling None as 0)
  • Never use ==, != or implicit false to compare with None. Use is or is not
if not users:
    print('no users')

if foo == 0:

if i % 10 == 0:

def f(x=None):
    if x is None:
        x = []


if len(users) == 0:
    print('no users')

if foo is not None and not foo:

if not i % 10:

def f(x=None):
    x = x or []

Do not use mutable objects or values that are evaluated at module load time as default values in function definition

Yes: def foo(a, b=None):
         if b is None:
             b = []
Yes: def foo(a, b: Optional[Sequence] = None):
         if b is None:
             b = []
Yes: def foo(a, b: Sequence = ()):  # Empty tuple OK since tuples are immutable
No:  def foo(a, b=[]):
No:  def foo(a, b=time.time()):  # The time the module was loaded???
No:  def foo(a, b=FLAGS.my_thing):  # sys.argv has not yet been parsed...

Add trailing commas if the closing bracket is on the next line of the last item

Yes:   golomb4 = [

No:    golomb4 = [

Always inherit from Object if a class has no other base classes

Yes: class SampleClass(object):

     class OuterClass(object):

         class InnerClass(object):

     class ChildClass(ParentClass):
         """Explicitly inherits from another class already."""

No: class SampleClass:

    class OuterClass:

        class InnerClass:

Do not use + and += on Strings (create temporary objects and results in quadratic running time)

Yes: items = ['<table>']
     for last_name, first_name in employee_list:
         items.append('<tr><td>%s, %s</td></tr>' % (last_name, first_name))
     employee_table = ''.join(items)

No: employee_table = '<table>'
    for last_name, first_name in employee_list:
        employee_table += '<tr><td>%s, %s</td></tr>' % (last_name, first_name)
    employee_table += '</table>'


Python __name__ = “__main__”

When a python file is executed python, a hidden variable named __name__ is set to __main__

print(__name__) # prints __main__

If is imported using import foo, then the __name__ variable is set to foo

if __name__ = "__main__" is used to check whether the current file is being run standalone or being imported. You can certainly fool python by assigning __main__ to __name__ manually:

__name__ = '__main__'

if __name__ = '__main__':
    print('running standalone')

File imports, when foo gets loaded, it will think it is running standalone and thus, print out running standalone.



Do not compare boolean variables to False using == in Python

Consider this snippet:

x = []
bool(x) # prints False
if x == False: # I know I should use `if not x`
    print('x == False') # prints nothing

Although the python documentation stated:

By default, an object is considered true unless its class defines either a bool() method that returns False or a len() method that returns zero’, Here are most of the built-in objects considered false:
* empty sequences and collections: ”, (), [], {}, set(), range(0)

There is no mention of why considered false does not equal to False. In later paragraphs of the same document:

Objects of different types, except different numeric types, never compare equal.

So comparing a list reference to False is wrong to begin with. I was thinking if that is the case then why True == 1 works, because bool and int are different objects right? Wrong according to this SO post:

False object is of type bool which is a subclass of int….booleans are explicitly considered as integers in Python 2.6 and 3.

Do not compare the following to False using ==, because even though they evaluate to false, they do not equal to False:

  • constants defined to be false: None and False.
  • zero of any numeric type: 00.00jDecimal(0)Fraction(0, 1)
  • empty sequences and collections: ''()[]{}set()range(0)

Another reason to not use == when comparing boolean is because it is redundant:

isClosed = True
if isClosed == True: # is equivalent of if True == True, it's like keep appending '== True'

The right way of checking boolean is simply:

if isClosed # when isClosed == True
if not isClosed # when isClosed == False

However, if not isClosed is checking isClosed == False and isClosed is None at the same time:

x = None
if not x:
    print('x is None') # This line gets printed

x = False
if not x:
    print('x is False') # This line gets printed

To make sure x is False but not None:

x = None
if x is not None and not x:
    print('x is not None and is False') # never printed

x = False
if x is not None and not x:
    print('x is not None and is False') # ✓

TypeError: something is not subscriptable

In layman’s terms: You are trying access me like a list but I don’t support that kind of functionality

Technically speaking: the object you called upon didn’t implement the __getitem()__ method.

A common cause of the error is when you are trying to access a sequence that is not ordered:

x = set([1,2,3])