SICP. 1.2.1
2022-11-13 Sun

Two meanings of `recursive' are distinguished. On the one hand, this word can be used to refer to processes that display a certain type of evolution. On the other hand, this word can be used to refer to procedures that display a certain syntactic feature. A recursive procedure does not always generate a recursive process.

Moreover, recursive processes are distinguished from iterative processes. One way to discover whether a process is recursive or iterative is to look at the ``shape'' we would draw if we employed the substitution model. Another way to see whether a process is recursive or iterative is to check whether, at any point of its evolution, knowing the state of the program variables is enough to know the state of the process at that point. If so, the process is iterative. Otherwise, it is recursive.

The concept of tail recursion is introduced.

Exercise 1.9

Exercise:

Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1. 

(define (+ a b)
  (if (= a 0) 
      b 
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0) 
      b 
      (+ (dec a) (inc b))))

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

Answer: 

(+ 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

Judging by its shape, it looks like we are dealing with a recursive process! 

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

Judging by its shape, it looks like we are dealing with an iterative process!

Exercise 1.10

Exercise:

The following procedure computes a mathematical function called Ackermann’s function. 

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions? 

(A 1 10)
(A 2 4)
(A 3 3)

Consider the following procedures, where A is the procedure defined above: 

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes \(5n^2\).

Answer: 

;; let's see the evolution of (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

We are looking at a recursive process. The answer is 1024. 

;; Let's do the same with (A 2 4).

(A 2 4)

(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

(A 1 (A 0 (A 0 (A 1 2))))

(A 1 (A 0 (A 0 (A 0 (A 1 1)))))

(A 1 (A 0 (A 0 (A 0 2))))

(A 1 (A 0 (A 0 4)))

(A 1 (A 0 8))

(A 1 16)

(A 0 (A 1 15))

(A 0 (A 0 (A 1 14)))

(A 0 (A 0 (A 0 (A 1 13))))

(A 0 (A 0 (A 0 (A 0 (A 1 12)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 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 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 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 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 (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 (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 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))

(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))

(A 0 (A 0 (A 0 (A 0 4096))))

(A 0 (A 0 (A 0 8192)))

(A 0 (A 0 16384))

(A 0 32768)

65536

Interesting shape… the answer is 65536. 

;; Let's see now the evolution of (A 3 3):

(A 3 3)

(A 2 (A 3 2))

(A 2 (A 2 (A 3 1)))

(A 2 (A 2 2))

(A 2 (A 1 (A 2 1)))

(A 2 (A 1 2))

(A 2 (A 0 (A 1 1)))

(A 2 (A 0 2))

(A 2 4) ;; We already know this one!

65536

Again 65536.

(f 1) is 2: 

(f 1)

(A 0 1)

2

(f 2) is 4: 

(f 2)

(A 0 2)

4

(f 3) is 6: 

(f 3)

(A 0 3)

(A 6)

I conclude that (f n) computes \(n \times 2\).

(g 1) is 2: 

(g 1)

(A 1 1)

2

(g 2) is 4: 

(g 2)

(A 1 2)

(A 0 (A 1 1))

(A 0 2)

4

(g 3) is 8: 

(g 3)

(A 1 3)

(A 0 (A 1 2)) ;; we already know that (A 1 2) is 4

(A 0 4)

8

(g 4) is 16: 

(g 4)

(A 1 4)

(A 0 (A 1 3)) ;; we already know that (A 1 3) is 8

(A 0 8)

16

Those are the powers of two. I conclude that (g n) computes \(2^n\).

(h 1) is 2: 

(h 1)

(A 2 1)

2

(h 2) is 4: 

(h 2)

(A 2 2)

(A 1 (A 2 1))

(A 1 2)

(A 0 (A 1 1))

(A 0 2)

4

(h 3) is 16: 

(h 3)

(A 2 3)

(A 1 (A 2 2))

(A 1 (A 1 (A 2 1)))

(A 1 (A 1 2))

(A 1 (A 0 (A 1 1)))

(A 1 (A 0 2))

(A 1 4) ;; we already know that (A 1 4) is 16

16

(h 4) is 65536. 

(h 4)

(A 2 4) ;; we know this one already...

65536

(h 5) is … 

(h 5)

(A 2 5)

(A 1 (A 2 4)) ;; (A 2 4) is 65536

(A 1 65536)

(A 0 (A 1 65535))

(A 0 (A 0 (A 1 65635))) ;; oh oh... this would take a while...

(h 4) is \(65536\), which is \(2^{16}\). (h 3) is \(16\), which is \(2^4\). (h 2) is \(4\), which is \(2^2\). My answer, then, is that (h n) computes \(n^{(h (1- n)))}\) where `(h (1- n))` is the application of h to n minus 1.

←

Please, send me an email if you have any comment.

Created with Emacs 28.2 (Org mode 9.5.5)