LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 February 20 2012

Joe
Member

[Exercise] Recursion, iteration, exponentiation.

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.

Offline

#2 February 21 2012

Joe
Member

Re: [Exercise] Recursion, iteration, exponentiation.

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.

Offline

#3 February 21 2012

geek
Member

Re: [Exercise] Recursion, iteration, exponentiation.

just a minor detail: fast_exp_iter(x, 0) should return 1, not x.
is this only applicable to tail recursion?

Offline

#4 February 21 2012

Joe
Member

Re: [Exercise] Recursion, iteration, exponentiation.

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

Offline

#5 February 21 2012

Joe
Member

Re: [Exercise] Recursion, iteration, exponentiation.

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.

Offline

#6 February 24 2012

arithma
Member

Re: [Exercise] Recursion, iteration, exponentiation.

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.

Offline

Board footer