Recursive to iterative using a systematic method

Question

I've started reading the book Systematic Program Design: From Clarity to Efficiency few days ago. Chapter 4 talks about a systematic method to convert any recursive algorithm into its counterpart iterative. It seems this is a really powerful general method but I'm struggling quite a lot to understand how it works.

After reading a few articles talking about recursion removal using custom stacks, it feels like this proposed method would produce a much more readable, optimized and compact output.

---

Recursive algorithms in Python where I want to apply the method

#NS: lcs and knap are using implicit variables (i.e.: defined globally), so they won't
#work directly

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

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

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

# i>=0, j>=0
def lcs(i,j):
    if i==0 or j==0:
        return 0
    elif x[i]==y[j]:
        return lcs(i-1,j-1)+1
    else:
        return max(lcs(i,j-1),lcs(i-1,j))

# i>=0, u>=0,  for all i in 0..n-1 w[i]>0
def knap(i,u):
    if i==0 or u==0:
        return 0
    elif w[i]>u:
        return knap(i-1,u)
    else:
        return max(v[i]+knap(i-1,u-w[i]), knap(i-1,u))

# i>=0, n>=0
def ack(i,n):
    if i==0:
        return n+1
    elif n==0:
        return ack(i-1,1)
    else:
        return ack(i-1,ack(i,n-1))

Step Iterate: Determine minimum increments, transform recursion into iteration

The Section 4.2.1 the book talks about determining the appropriate increment:

1) All possible recursive calls
    fact(n)   => {n-1}
    fib(n)    => {fib(n-1), fib(n-2)}
    bin(n,k)  => {bin(n-1,k-1),bin(n-1,k)}
    lcs(i,j)  => {lcs(i-1,j-1),lcs(i,j-1),lcs(i-1,j)}
    knap(i,u) => {knap(i-1,u),knap(i-1,u-w[i])}
    ack(i,n)  => {ack(i-1,1),ack(i-1,ack(i,n-1)), ack(i,n-1)}

2) Decrement operation
    fact(n)   => n-1
    fib(n)    => n-1
    bin(n,k)  => [n-1,k]
    lcs(i,j)  => [i-1,j]
    knap(i,u) => [i-1,u]
    ack(i,n)  => [i,n-1]

3) Minimum increment operation
    fact(n)   => next(n) = n+1
    fib(n)    => next(n) = n+1
    bin(n,k)  => next(n,k) = [n+1,k]
    lcs(i,j)  => next(i,j) = [i+1,j]
    knap(i,u) => next(i,u) = [i+1,u]
    ack(i,n)  => next(i,n) = [i,n+1]

Section 4.2.2 talks about forming the optimized program:

Recursive
---------
def fExtOpt(x):
    if base_cond(x) then fExt0(x )       -- Base case
    else let rExt := fExtOpt(prev(x)) in -- Recursion
        f Ext’(prev(x),rExt)              -- Incremental computation

Iterative
---------
def fExtOpt(x):
    if base_cond(x): return fExt0(x)                    -- Base case
    x1 := init_arg; rExt := fExt0(x1)                   -- Initialization
    while x1 != x:                                      -- Iteration
        x1 := next(x1); rExt := fExt’(prev(x1),rExt)    -- Incremental comp
    return rExt

How do I create {fibExtOpt,binExtOpt,lcsExtOpt,knapExtOpt,ackExtOpt} in Python?

Additional material about this topic can be found in one of the papers of the main author of the method, Y. Annie Liu, Professor.

Answer 1

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.