6. Recursion vs. Iteration

 

 

 

 

Recursion vs. Iteration¶

A recursive function is concptually clean.

 

In [1]:

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

 

 

120

 

 

However, it is relatively expensive because of the creation and manipulation of stack frames. You can visualize its execution here.

For better efficiency, we can convert the function to use iteration instead

Approach 1: Brute Force Using Stack¶

We can use a stack data structure to simulate the stack frames of the recursive call. This is tedious and not particularly efficient.

 

In [2]:

def factorial_stack(n):
    stack = []
    stack.append(n)
    state = 'Pre'

    while True:
        if state == 'Pre':
            if n > 2:
                n = n - 1
                stack.append(n)
            else:
                state = 'Post'
        else:
            result = stack.pop()
            if not stack:
                break
            n = stack.pop()
            stack.append(n * result)

    return result

print(factorial_stack(5))

 

 

120

 

 

Approach 2: Convert into Tail Calls¶

Step 1: Convert recursive calls into tail calls with return statement.

 

In [3]:

def factorial1a(n, acc=1):
    if n < 2:
        return 1 * acc
    return factorial1a(n - 1, acc * n)
    
print(factorial1a(5))

 

 

120

 

 

Step 2: Enclose function body in while True:

 

In [4]:

def factorial1b(n, acc=1):
    while True:
        if n < 2:
            return 1 * acc
        return factorial1a(n - 1, acc * n)

print(factorial1b(5))

 

 

120

 

 

Step 3: Replace all recursive tail calls f(x=x1, y=y1, ...) with x, y, ... = x1, y1, .... Be sure to update all arguments in the assignment.

 

In [5]:

def factorial1c(n, acc=1):
    while True:
        if n < 2:
            return 1 * acc
        n, acc = n - 1, acc * n

print(factorial1c(5))

 

 

120

 

 

Step 4: Clean up the code to make it more idiomatic.

 

In [6]:

def factorial1d(n):
    acc=1
    while n>1:
        n, acc = n - 1, acc * n
    return acc

print(factorial1d(5))

 

 

120

 

 

Now the stack size from is reduced from O(n) to O(1). You can visualize its execution here.