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`

.