[Solved] Recursive to iterative using a systematic method [closed]

Question

So, to restate the question. We have a function f, in our case fac.

def fac(n):
    if n==0:
        return 1
    else:
        return n*fac(n-1)

It is implemented recursively. We want to implement a function facOpt that does the same thing but iteratively. fac is written almost in the form we need. Let us rewrite it just a bit:

def fac_(n, r):
    return (n+1)*r

def fac(n):
    if n==0:
        return 1
    else:
        r = fac(n-1)
        return fac_(n-1, r)

This is exactly the recursive definition from section 4.2. Now we need to rewrite it iteratively:

def facOpt(n):
    if n==0:
        return 1
    x = 1
    r = 1
    while x != n:
        x = x + 1
        r = fac_(x-1, r)
    return r

This is exactly the iterative definition from section 4.2. Note that facOpt does not call itself anywhere. Now, this is neither the most clear nor the most pythonic way of writing down this algorithm — this is just a way to transform one algorithm to another. We can implement the same algorithm differently, e.g. like that:

def facOpt(n):
    r = 1
    for x in range(1, n+1):
        r *= x 
    return r

Things get more interesting when we consider more complicated functions. Let us write fibObt where fib is :

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

fib calls itself two times, but the recursive pattern from the book allows only a single call. That is why we need to extend the function to returning not one, but two values. Fully reformated, fib looks like this:

def fibExt_(n, rExt):
    return rExt[0] + rExt[1], rExt[0]

def fibExt(n):
    if n == 0:
        return 0, 0
    elif n == 1:
        return 1, 0
    else:
        rExt = fibExt(n-1)
        return fibExt_(n-1, rExt)

def fib(n):
    return fibExt(n)[0]

You may notice that the first argument to fibExt_ is never used. I just added it to follow the proposed structure exactly.
Now, it is again easy to turn fib into an iterative version:

def fibExtOpt(n):
    if n == 0:
        return 0, 0
    if n == 1:
        return 1, 0
    x = 2
    rExt = 1, 1
    while x != n:
        x = x + 1
        rExt = fibExt_(x-1, rExt)
    return rExt

def fibOpt(n):
    return fibExtOpt(n)[0]

Again, the new version does not call itself. And again one can streamline it to this, for example:

def fibOpt(n):
    if n < 2:
        return n
    a, b = 1, 1
    for i in range(n-2):
        a, b = b, a+b
    return b

The next function to translate to iterative version is bin:

def bin(n,k):
    if k == 0 or k == n:
        return 1
    else:
        return bin(n-1,k-1) + bin(n-1,k)

Now neither x nor r can be just numbers. The index (x) has two components, and the cache (r) has to be even larger. One (not quite so optimal) way would be to return the whole previous row of the Pascal triangle:

def binExt_(r):
    return [a + b for a,b in zip([0] + r, r + [0])]

def binExt(n):
    if n == 0:
        return [1]
    else:
        r = binExt(n-1)
        return binExt_(r)

def bin(n, k):
    return binExt(n)[k]

I have’t followed the pattern so strictly here and removed several useless variables. It is still possible to translate to an iterative version directly:

def binExtOpt(n):
    if n == 0:
        return [1]
    x = 1
    r = [1, 1]
    while x != n:
        r = binExt_(r)
        x += 1
    return r

def binOpt(n, k):
    return binExtOpt(n)[k]

For completeness, here is an optimized solution that caches only part of the row:

def binExt_(n, k_from, k_to, r):
    if k_from == 0 and k_to == n:
        return [a + b for a, b in zip([0] + r, r + [0])]
    elif k_from == 0:
        return [a + b for a, b in zip([0] + r[:-1], r)]
    elif k_to == n:
        return [a + b for a, b in zip(r, r[1:] + [0])]
    else:
        return [a + b for a, b in zip(r[:-1], r[1:])]

def binExt(n, k_from, k_to):
    if n == 0:
        return [1]
    else:
        r = binExt(n-1, max(0, k_from-1), min(n-1, k_to+1) )
        return binExt_(n, k_from, k_to, r)

def bin(n, k):
    return binExt(n, k, k)[0]

def binExtOpt(n, k_from, k_to):
    if n == 0:
        return [1]
    ks = [(k_from, k_to)]
    for i in range(1,n):
        ks.append((max(0, ks[-1][0]-1), min(n-i, ks[-1][1]+1)))
    x = 0
    r = [1]
    while x != n:
        x += 1
        r = binExt_(x, *ks[n-x], r)
    return r

def binOpt(n, k):
    return binExtOpt(n, k, k)[0]

In the end, the most difficult task is not switching from recursive to iterative implementation, but to have a recursive implementation that follows the required pattern. So the real question is how to create fibExt', not fibExtOpt.

Accepted Answer