A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

**Joe****Member**

The goal of this exercise is to highlight the difference between the recursive definition of a procedure, and the recursive evolution of a process. From SICP:

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process

with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to

the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself.

But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking

about how the process evolves, not about the syntax of how a procedure is written.

In order to understand this better, we will work on the implementation of the exponentiation function.

We can do this by noticing that:

```
exp(x,y) = x * exp(x, y-1)
exp(x, 0) = 1
we're assuming that both x and y are integers with x > 0 and y >= 0
```

A straightforward recursive way of writing this in Python:

```
define exp (x, y):
if y == 0:
return 1
return x * exp (x, y-1)
```

Another way of implementing this could be:

```
define exp-iter (x, y, count, product):
if count > y:
return product
return exp-iter (x, y, count+1, x*product)
define exp (x, y):
return exp-iter (x, y, 1, x)
```

Note that despite the recursive definition, the function **exp-iter** is actually evolving iteratively. A simple way to see this is that unlike its recursive counterpart, exp-iter holds the whole state of the computation in its arguments. The recursion is just a syntactic tool for looping over the set [1 .. y]. Modern languages like Python will use **for** loops instead:

```
define exp-iter (x,y):
product = 1
for count in range(y):
product *= x
return product
```

*Notice that the two implementations of exp-iter are exactly equivalent.*

If we compare the complexity of the recursive and the iterative approach, we will find that they will both find the result in the same number of steps - O(y). However, they have different space (memory) complexity. The recursive way will have a O(y) complexity, whereas the iterative way will grow constantly, O(1).

**Exercise**

We will try to improve the complexity by noticing that:

```
exp (x, y) = exp (x, y/2) * exp (x, y/2) if y is even
exp (x, y) = x * exp (x, y-1) if y is odd
```

For instance:

exp(x, 8) = exp(x, 4) * exp (x, 4)

= square (exp (x, 4))

Implementing this in Python:

```
define square(x):
return x*x
define fast-exp (x, y):
if y == 0:
return 1
if y%2==0:
return square (fast-exp (x, y/2))
else:
return x * fast-exp (x, y-1)
```

The new procedure fast-exp will compute in O(log(n)) steps which is an improvement over the early one. However it is recursive, and therefore will not be constant in space when growing. Hence, the following exercise:

**Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt**

**NB:** I clearly did not come up with this exercise; I have simply summarized an exercise available in the famous book mentionned above. I will post my solution, as well as links to other solutions found online, tonight.

**Joe****Member**

A little disappointed nobody seems to be interested in my super exercise :'(

Here's my solution anyway in Python:

```
def fast_exp_iter (x, y, z=1):
if y == 0 and x != 0:
return 1
if y == 1:
return z*x
if y%2 == 0:
return fast_exp_iter (x*x, y/2, z)
else:
return fast_exp_iter (x, y-1, z*x)
```

Feel free to comment on or criticize it.

**geek****Member**

just a minor detail: fast_exp_iter(x, 0) should return 1, not x.

is this only applicable to tail recursion?

**Joe****Member**

Corrected, I added one more if statement. I cannot find a simpler (more concise) way to do it.

**Joe****Member**

is this only applicable to tail recursion

I'm not sure I understand your question but it got me thinking.

I'm not sure whether you meant: *"Can we translate a non-tail recursive process into an iterative one?"*.

Then again how difficult is it to implement an iterative Fibonacci sequence?

**EDIT:** Never mind what I wrote, the following exercise made us apply the same squaring approach on Fibonacci's sequence. Here's the code I came up with:

```
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (square p) (square q))
(+ (* 2 q p) (square q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
```

Much easier to see in tail recursive processes, I needed serious hand holding in order to produce the above code.

**arithma****Member**

A little disappointed nobody seems to be interested in my super exercise :'(

I am interested. Don't cry. But it's just time that's constrained over here a bit.