SICP - 1.9 -- 1.10

1.9

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?

***

Egy kis gondolkodással látható, hogy az első process rekurzív a második pedig iteratív, de
ha behelyettesítgetjük, akkor látni is fogjuk az ismerős alakot:

;; elso definicio szerint (rekurziv)

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

;; a masodik definicio szerint (iterativ)

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

1.10

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.

***

Ebben a feladatban az a jó, hogy papíron is rá lehet jönni (így is csináltam) és felesleges teljesen
kiszámolni.

1. (A 1 10)

   -->

   (A 0 (A 1 9))

   -->

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

   --> érdekes, mi lehet a pattern?
   Nézzük meg először, hogy mit ad vissza az

   (A 1 1)

   -- hiszen úgy is el fogunk jutni
   hozzá: a szabályok szerint egy 2-est. A fenti pattern szerint lesz 9 darab

   ...(A 0...

   a kifejezésünkben meg egy kettes a végén. És a definíció szerint ha

   (A 0 x)

   akkor

   (* 2 x)

   , tehát 2^10-t kapunk.

2. A megoldásból látható, hogy a
   

   g

   függvény (

   (define (g n) (A 1 n))

   , ugye)
   ezt csinálja: g(n) = 2^n

3. (A 2 4)

   -->

   (A 1(A 2 3))

   --> oké, akkor itt

   ...(A 1...

   -ek
   sorozatát fogjuk kapni. Mi lesz ha a végén elérjük

   ...(A 2 1)...

   -et? Kapunk egy kettest, oké.
   Akkor az előző megoldásból következően egy négyes hatványtornyot fogunk kapni:

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

4. Ebből pedig azt is látjuk, hogy a
   

   (define (h n) (A 2 n))

   definíció a 2 tetrációját
   adja meg, amit így tudnék közelíteni: h(n) = 2^...n-szer...^2

5. 
   (A 3 3)
   (A 2 (A 3 2))
   (A 2 (A 2 (A 3 1))
   (A 2 (A 2 2))
   (A 2 2^2)
   2^2^2^2 ;; mert a 2 2^2-ik tetráltjat kerestuk, ugye
   

6. (define (f n) (A 0 n))

   esetén pedig f(n) = 2n