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:

 

Cheng

 

Leave a Reply

Your email address will not be published. Required fields are marked *

Bitnami