# SICP Solutions

### Chapter 5, Computing with Register Machines

#### Exercise 5.34

That’s interesting.

How to spot the code which is causing the process to be iterative?

As we saw in the tail recursion in section 5.5.3 under heading Applying compiled procedure, pg-586:

Because of Tail call optimisation, we can have two cases while applying a procedure:

• If the linkage is label:
• If the linkage is return:

Now, consider what happen if the procedure is iterative:

The last expression executed in the procedure must cause return to the previous continue point without introducing any new points of returns.

Lets see the given iter, an iterative case, to understand:

There is only one expression, if inside which for the false case we have a recursive invocation. Now this recursive invocation because of the book’s tail call optimization will cause to return to the same place continue from where we invoked iter.

But what will happen for the recursive process case:

The last expression here also is if and the recursive call happens in the false branch of if. Now notice that here continue after invocation of factorial will need to return to the place where we are creating argl for *.

Thus for every recursive call in this case will cause to save a continue on the stack!

This was not the case in iterative version because continue is always same in each recursive call!

#### To summarise:

The iterative procedure will generate recursive call as:

while the recursive version will generate the recursive call as:

Now we can see this in the assembly code generated:

Which place we need to see? Yes, the false branch case where recursive call is made in both iterative and recursive cases!

#### Let’s first see the iterative case code(check under false branch):

Note that in the above code the stack has same number of elements before and after each invocation of iter.

Now, let’s see the recursive case(again just see the code under false branch):

Note that in this case after each invocation of factorial the number of elements in stack keeps growing till last recursive invocation and then the stack is unwind while performing the computations for *.