Each of the following two procedures defines a method for adding two
positive integers in terms of the procedure inc, which
increments its arguments by 1, and dec, which decrements is
arguments 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?
The first procedure evolves the following recursive process
(+ 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)
; 9The second procedure evolves the following iterative process
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
; 9The 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$.
From the definition of A, (f n) is clearly $2n$.
(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 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 512)
; 1024From the evolution of this process we see that (g n) results in
$2^n$
(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 4))
(A 1 16)
; 65536From the evolution of this process we see that (h n) results in