Transforming recursion into iteration

I've got the following question on a job interview:

"A box contain a number of chocolates that can only be removed 1 at a time or 3 at a time. How many ways can the box be emptied?"

At first, I tried to do it with recursion, and it worked. This is the following python code:

def numberOfWays(n):
    if n <= 2:
        return 1
    else:
        return numberOfWays(n - 3) + numberOfWays(n - 1)

However, the website didn't allow the use of recursion. I've tried it many times, but I just couldn't turn it into an iterative function, since on the original function, I have to output two results.

This problem is very similar to Fibonacci and you can create an iterative solutions that is much more performant than the recursive solution. I modified the recursive function a little bit because from reading the question I interpret n = 0 as having 0 ways to empty the box by removing 1 or 3 items. Here is the modified recursive function.

def numberOfWays(n):
if n <= 0:
    return 0
elif n in (2, 1):
    return 1
elif n == 3:
    return 2
else:
    return numberOfWays(n - 3) + numberOfWays(n - 1)

Here is an iterative solution that will use less memory than the one Michael provided since it only stores 3 numbers instead of every single number in the series up to n:

def numberOfWays(n):
if n == 0:
    return 0
elif n <= 2:
    return 1
elif n == 3:
    return 2
a, b, c, = 1, 1, 2
for i in range(n-3):
    a, b, c, = b, c, c + a

return c

I counted the number of loop iterations for the iterative function and the number of function calls for the recursive one to show how much better it performs.

Iterative
n of 10 = 28 | Loop Iterations: 7
n of 9 = 19 | Loop Iterations: 6
n of 8 = 13 | Loop Iterations: 5
n of 7 = 9 | Loop Iterations: 4
n of 6 = 6 | Loop Iterations: 3
n of 5 = 4 | Loop Iterations: 2
n of 4 = 3 | Loop Iterations: 1
n of 3 = 2 | Loop Iterations: 0
n of 2 = 1 | Loop Iterations: 0
n of 1 = 1 | Loop Iterations: 0
n of 0 = 0 | Loop Iterations: 0

Recursive:
n of 10 = 28 | Function calls: 37
n of 9 = 19 | Function calls: 25
n of 8 = 13 | Function calls: 17
n of 7 = 9 | Function calls: 11
n of 6 = 6 | Function calls: 7
n of 5 = 4 | Function calls: 5
n of 4 = 3 | Function calls: 3
n of 3 = 2 | Function calls: 1
n of 2 = 1 | Function calls: 1
n of 1 = 1 | Function calls: 1
n of 0 = 0 | Function calls: 1

Caching/Memoizing the result would be good if this function were used in software where it will be called many times with the same parameters regardless of the underlying implementation. However this probably won't help you pass all the automated tests in an online coding challenge.

Translating your recursive algorithm into a naive iterative solution will still have runtime complexity of O(2^n).

def NoW_iter(n):
    if n <= 2: return 1
    c = 2
    l = [n-3, n-1]
    while l:
        i = l.pop()
        if i > 2:
            c += 1
            l += [i-3, i-1]
    return c

An easy way to fix runtime issues for your algorithm would be to memoize interim results

from functools import lru_cache

@lru_cache(maxsize=None)
def numberOfWays(n):
    if n <= 2:
        return 1
    else:
        return numberOfWays(n - 3) + numberOfWays(n - 1)

This can be done in an iterative approach as well with a runtime complexity of O(n).

def NoW_memo(n):
    d = {0: 1, 1: 1, 2: 1}
    for i in range(3, n+1):
        d[i] = d[i-3] + d[i-1]
    return d[n]

Transforming recursion into iteration

Related

Recent Posts