SICP Series-chapter 1.2.1-1.2.2

When we talk about the recursive, factorial is one of the most classical problem. In the LISP world, recursive is very normal, but you also can use the “iterative process”. But this is a special iterative process. You can take a look at the example below to compare it with others which are written by other programming language.
(defun fact-iter(product iter maxiter)
  (if (> iter maxiter)
      product
      (fact-iter (* product iter)
                 (+ iter 1)
                 maxiter)))

(defun fact (n)
  (fact-iter 1 1 n))

1.9 The first one is recursive, the second one is iterative.

1.10

(defun A (x y)
  (cond ((= y 0) 0)
        ((= x 0) (* y 2))
        ((= y 1) 2)
        (t (A (- x 1)
              (A x (- y 1))))))

(A 1 10)
(A 0 (A 1 9))
(* 2 (A 1 9))
(* 2 (A 0 (A 1 8)))
(* 2 (* 2 (A 1 8)))
….
You can see that the (A 1 10)=2^10

(defun f (n) (A 0 n)) ;2n
(defun g (n) (A 1 n));2^n
(defun h (n) (A 2 n)); 2^2^… (n times)

Another common pattern of computation is called tree recursive, Fibonacci is one of the most classical example.
1.11 Tree recursive is very inefficiency, when I take the n as 100, my laptop runs for a very long time. When I use the iterative version, even the n is 10000, it takes less then one second. You can see the run-time information when the n=2000 and n=20. You will see the big gap between them.

(defun f-rec(n)
    (cond ((< n 3) n)
           (t (+ (f-rec (- n 1))
                 (* 2 (f-rec (- n 2)))
                 (* 3 (f-rec (- n 3)))))))
 
(defun f-iter(n)
    (if (< n 3)
        n
        (f-iter-aux 2 1 0 n)))
 
(defun f-iter-aux (a b c n)
    (if (= n 2)
        a
        (f-iter-aux (+ a
                        (* 2 b)
                        (* 3 c))
                    a
                    b
                    (- n 1))))

1.12 This exercise is very similar to the Fibonacci
(defun pascal (positionr positionc)
    (cond ((= positionr 1) 1)
          ((= positionc positionr) 1)
          ((= positionc 1) 1)
          (t (+ (pascal (- positionr 1) positionc)
                (pascal (- positionr 1) (- positionc 1))))))