# SICP1.2.1 Recursion & Iteration

Published: 2020-06-14T18:28:16.000Z

Ok, second subchapter is more challenging, so I'll go by subsections.

## Exercise 1.9

This is trivial. This procedure generates recursive process:

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

And this iterative:

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

We could see this even without substitution model, if function returns itself in the and without any additional operation on its result - it is tail-recursive, so generates iterative process, otherwise - recursive.

## Exercise 1.10 (Ackerman function)

``````(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))``````
``````(A 1 10)
=> (A 0 (A 1 9))
=> (* 2 (A 1 9))
=> (* 2 (*2 (A 1 8)))
...
=> (* 2^9 (A 1 1))
=> 2^10``````
``````(A 2 4)
=> (A 1 (A 2 3))
=> 2^(A 2 3)
;;; see below ;;;
=> 2^16``````
``````(A 2 3)
=> (A 1 (A 2 2))
=> 2^(A 2 2)
;;; see below ;;;
=> 2^4 => 16``````
``````(A 2 2)
=> (A 1 (A 2 1))
=> (A 1 2)
=> (A 0 (A 1 1))
=> (* 2 2)
=> 4``````
``````(A 3 3)
=> (A 2 (A 3 2))
=> (A 2 (A 2 (A 3 1)))
=> (A 2 (A 2 2))
;;; see one above ;;;
=> (A 2 4)
;;; see 3 above ;;;
=> 2^16``````
``(define (f n) (A 0 n))``

`f(n) = 2n`

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

`g(n) = 2^n`

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

`h(1) = 2` `h(n) = 2^(h(n-1))`