SICP Solutions: Sections 1.2.1 and 1.2.2
Section 1.2
Section 1.2.1
Exercise 1.9
First procedure:
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
Second procedure:
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8
(+ 0 9)
9
The first process is a linear recursive process. The second process is a linear iterative process.
Hint: try to see whether calling itself is absolutely the last thing a procedure does.
Exercise 1.10
Expression (A 1 10)
:
(A 1 10)
(A 0
(A 1 9))
(A 0
(A 0
(A 1 8
(A 0
(A 0
(A 0
(A 1 7))))
(A 0
(A 0
(A 0
(A 0
(A 1 6)))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 1 5))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 1 4)))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 1 3))))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 1 2)))))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 1 1))))))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0 2)))))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0 4))))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0 8)))))))
(A 0
(A 0
(A 0
(A 0
(A 0
(A 0 16))))))
(A 0
(A 0
(A 0
(A 0
(A 0 32)))))
(A 0
(A 0
(A 0
(A 0 64))))
(A 0
(A 0
(A 0 128)))
(A 0
(A 0 256))
(A 0 512)
1024
So (A 1 x)
is \(2^x\).
Expression (A 2 4) |
: |
(A 2 4)
(A 1
(A 2 3))
;; So this is 2^(A 2 3), let's see
(A 2 3)
(A 1
(A 2 2))
;; So 2^(2^(A 2 2))
(A 2 2)
(A 1
(A 2 1))
;; So 2^(2^(2^(A 2 1)))
(A 2 1)
2
;; So finally 2^(2^(2^2))
;; Or 2^(2^4)
;; Or 2^16
;; 65,636
So (A 2 x)
is 2 to the power of 2, to the power of 2 .. x
times.
Expression (A 3 3)
:
(A 3 3)
(A 2
(A 3 2))
;; We know what (A 2 x) is, 2 to the power of 2 x times.
;; Let's see where (A 3 2) takes us:
(A 3 2)
(A 2
(A 3 1))
(A 2 2)
;; Which is 2^2
;; and the starting expression is (A 2 4)
;; Which is exactly the same as before.
So again (A 3 3)
equals \(2^{16} = 65,636\).
(f n)
computes \(2n\).(g n)
computes \(2^n\).(h n)
computes 2 to the power of 2, to the power of 2 ..x
times.
Section 1.2.2
Exercise 1.11
Recursive process:
(define (f n)
(if (< n 3)
n
(+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
(f 4)
Iterative process:
(define (f n)
(if (< n 3)
n
(f-iter 2 1 0 (- n 2))))
(define (f-iter a b c count)
(if (= count 0)
a
(f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))
(f 4)
Exercise 1.12
We define a procedure pascal
that accepts a row and a column as arguments:
(define (pascal x y)
(if (or (= y 0) (= x y))
1
(+ (pascal (- x 1) (- y 1))
(pascal (- x 1) y))))
(pascal 3 2)
Exercise 1.13
First, the induction.
The base step, for \(n = 0\):
\[\mathrm{Fib}(0) = (\phi^0 - \psi^0) / \sqrt{5} = 0 \textrm{, it holds.}\]Assume it is true for \(n\), we will prove that it is true for \(n + 1\):
\[\begin{align*} \mathrm{Fib}(n+1) &= \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}}\\ \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}} &= \mathrm{Fib}(n) + \mathrm{Fib}(n - 1)\\ \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}} &= \frac{\phi^n - \psi^n}{\sqrt{5}} + \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}}\\ \phi^{n+1} - \psi^{n+1} &= \phi^n - \psi^n + \phi^{n-1} - \psi^{n-1}\\ \phi^{n-1}(\phi^2 - \phi - 1) &= \psi^{n-1}(\psi^2 - \psi - 1) \end{align*}\]By definition, \(\phi^2 = \phi + 1\). Notice that also \(\psi^2 = \psi + 1\). This means that both sides of the equation are $0$, and the induction holds.
We have proven that
\[\begin{equation*} \mathrm{Fib}(n) = \frac{\phi^n - \psi^n}{\sqrt{5}} \end{equation*}\]Now we need to prove that \(\vert\frac{\psi^n}{\sqrt{5}}\vert < \frac{1}{2}\).
Notice that \(\psi < \frac{1}{2}\), and hence \(\vert\psi^{n+1}\vert < \vert\psi^n\vert, \forall n \in N\). Since \(\vert\frac{\psi^0}{\sqrt{5}}\vert < \frac{1}{2}\), it holds for all the rest values of \(n\).