# SICP Solutions

### Chapter 5, Computing with Register Machines

#### Exercise 5.28

Thus we get the following table:

Max-depth(no tail optimz) Max-depth(with tail optimz) num-pushes(no tail optimz) num-pushes(with tail optimz)
Recursive factorial $\, \text{maximum-depth} = 8n+3 \,$ $\, \text{maximum-depth} = 5n+3 \,$ $\, \text{total-pushes} = 34n - 16 \,$ $\, \text{total-pushes} = 32n - 16 \,$
Iterative factorial $\, \text{maximum-depth} = 3n+14 \,$ $\, \text{maximum-depth} = 10 \,$ $\, \text{total-pushes} = 37n + 33 \,$ $\, \text{total-pushes} = 35n + 29 \,$
• Clearly, without tail optimization we have linear dependency on n for space(max-depth).
• Even the iterative version is no longer independent of n.
• Even in the recursive version there is an extra cost added in the no-tail-optimized, compared to the recursive version with tail-optimized. So tail-optimization helps even in recursive version!