(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))
(define (distance-from-origin x y)
  (sqrt (sum-of-squares x y)))

(define (abs x)
  (cond ((< x 0) (- x))
	(else x)))

(define (sum-of-sq-of-two-larger-numbers a b c)
  (if (< a b)
      (if (< a c)
	  (sum-of-squares b c)
	  (sum-of-squares a b))
      (if (< b c)
	  (sum-of-squares a c)
	  (sum-of-squares a b))))

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

;; recursive definition of factorial
;; a simple example of linear recursive process.
(define (factorial n)
  (if (zero? n)
      1
      (* n (factorial (- n 1)))))

;; linear iterative process . tail recusive procedure.
(define (factorial-iter n)
  (define (fact-iter accum count num)
    (if (= count num)
	accum
	(fact-iter (* accum (+ count 1))
		   (+ count 1)
		   num)))
  (fact-iter 1 1 n))

(define (make-serial-number-generator)
  (let ((current-number 0))
    (lambda ()
      (set! current-number (+ current-number 1))
      current-number)))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
		 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

;; 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))))))
(define (f n) (A 0 n));; computes 2n
(define (g n) (A 1 n));; computes 2^n
(define (h n) (A 2 n))
;; gives exponential recursion func i.e., (h n)= 2^(h (- n 1))
;; mathematically concise definition would be 2^2^2...^2 n-1 2's

;;; Tree recursion.
(define (fibonacci n)
  (cond ((= n 0) 1)
	((= n 1) 1)
	(else (+ (fibonacci (- n 1))
		 (fibonacci (- n 2))))))

;; iterative process with 3 state variables.
(define (fibonacci-iter n)
  (define (fib-iter a b count)
    (if (= count 0)
	b
	(fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

;;; Counting change.
;; write a procedure to compute the number of ways to change
;; any given amount of money.

(define (count-change amount denominations)
  (cond ((null? denominations) 0)
	((zero? amount) 1)
	((< amount 0) 0)
	(else (+ (count-change amount (cdr denominations)); without the first denomination.
		 (count-change (- amount (car denominations)) denominations) ; with one first denomination.
		 ))))

;; TODO: write the above function as an iterative process.


;;; exercise 1.11 f(n) = f(n-1) + 2*f(n-2) + 3*f(n-3)
;; write a procedure to compute f(n) by an iterative process
;; tree recusive procedure
(define (f-1-11 n)
  (cond ((= n 1) 1)
	((= n 2) 2)
	((= n 3) 3)
	(else (+ (f-1-11 (- n 1))
		 (* 2 (f-1-11 (- n 2)))
		 (* 3 (f-1-11 (- n 3)))))))
;; iterative procedure
(define (f-1-11-iter n)
  (define (f-iter a b c d count)
    (if (zero? count)
	a
	(f-iter (+ a (* 2 b) (* 3 c)) a b c (- count 1))))
  (cond ((= n 1) 1)
	((= n 2) 2)
	((= n 3) 3)
	(else (f-iter 10 3 2 1 (- n 4)))))

;;; exercise 1.12 pascal's triangle
;; write a procedure that computes the elements of pascal's triangle by
;; means of a recursive process.
(define (pascals-triangle n)
  (define (row n)
    (if (= n 1)
	(quote (1))
	(let ((prev (row (- n 1))))
	  (zip-dis prev (cons 0 prev) '()))))
  (define (zip-dis l r accum)
    (cond ((null? l) (catenate r accum))
	  ((null? r) (catenate l accum))
	  (else (zip-dis (cdr l)
			 (cdr r)
			 (cons (+ (car l) (car r)) accum)))))
  (define (catenate l r)
    (if (null? l)
	r
	(catenate (cdr l) (cons (car l) r))))
  (row n))

;;; 1.3 Orders of growth.
;; TODO: what's wrong with this function?
(define (sine x)
  (define (f1 a)
    (- (* 3 x)
       (* 4 x x x)))
  (define (abs a)
    (if (< a 0)
	(- a)
	a))
  (if (< (abs x) 0.1)
      x
      (f1 (sine (/ x 3.0)))))

;;; 1.4 exponentiation
(define (my-expt x y)
  (if (= y 0)
      1
      (* x (my-expt x (- y 1)))))

;; iteration procedure defined outside for better ,trace
(define (my-expt-iter-a x y accum)
  (if (= y 0)
      accum
      (my-expt-iter-a x (- y 1) (* accum x))))
(define (my-expt-iter x y)
  (my-expt-iter-a x y 1))

(define (fast-expt x y)
  (cond ((= y 0) 1)
	((even? y) (square (fast-expt x (/ y 2))))
	((odd? y) (* x (square (fast-expt x (/ (- y 1) 2)))))
	(else (error "wrong exponent"))))
;; exercise 1.16
;; design a procedure that evolves an iterative exponentiation process using
;; successive squaring and uses logarithmic number of steps, similar to fast-expt
(define (fast-expt-iter a b accum)
  (cond ((= b 0) accum)
	((even? b) (fast-expt-iter (* a a) (/ b 2) accum)) ; finding an invariant in state vars
	(else (fast-expt-iter a (- b 1) (* a accum)))))
(define (fast-expt-i x y)
  (fast-expt-iter x y 1))