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: 