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
total += n # the base case
return sum(n-1, total) # total is used to maintain the state

# simplified version
def sum(n, total=0):
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:

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.

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))

Don’t

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(): ...

Don’t

for key in adict.keys(): ...
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:
self.handle_zero()

if i % 10 == 0:
self.handle_multiple_of_ten()

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

Don’t:

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

if foo is not None and not foo:
self.handle_zero()

if not i % 10:
self.handle_multiple_of_ten()

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 = [
0,
1,
4,
6,
]

No:    golomb4 = [
0,
1,
4,
6
]

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

Yes: class SampleClass(object):
pass

class OuterClass(object):

class InnerClass(object):
pass

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

No: class SampleClass:
pass

class OuterClass:

class InnerClass:
pass

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))
items.append('</table>')
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>'

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

# foo.py
print(__name__) # prints __main__

If foo.py 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:

# foo.py
__name__ = '__main__'

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

#bar.py
import foo.py

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

Reference

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)

https://docs.python.org/3/library/stdtypes.html#truth-value-testing

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') # ✓

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])
x 