Hailperin, Chapter 2

Slides, Recursive definition of factorial.

(define factorial
    (lambda (n)
      (if (= n 1)
          1
          (* (factorial (- n 1)) n))))

> (factorial 10)
> (factorial 20)
> (factorial 40)

etc.

Slides, Squaring a number recursively without multiplication.

(define square
  (lambda (n)
    (if (= n 0)
        0
        (+ (square (- n 1))
           (- (+ n n) 1)))))

Slides, Prove that square is correct.

> (quotient 9 3)
> (quotient 10 3)
> (quotient 11 3)
> (quotient 12 3)
> (quot 9 3)  Error

Now, define quot

Based on the idea:

(quot 11 3) returns same as (quot 8 3) + 1 because 11 is greater than or equal to 3

(define quot
  (lambda (n d)
    (if (< n d)
        0
        (+ 1 (quot (- n d) d)))))
 
Problem:
Does not work with either argument negative.

(define quot
  (lambda (n d)
    (if (< d 0)
        (- (quot n (- d)))
        (if (< n 0)
            (- (quot (- n) d))
               (if (< n d)
                   0
                   (+ 1 (quot (- n d) d)))))))

> (quot 11 3)
> (quot 11 -3)
> (quot -11 3)
> (quot -11 -3)

Slide: The cond function

(define quot
  (lambda (n d)
    (cond ((< d 0) (- (quot n (- d))))
          ((< n 0) (- (quot (- n) d)))
          ((< n d) 0)
          (else (+ 1 (quot (- n d) d))))))

> (quot 11 3)
> (quot 11 -3)
> (quot -11 3)
> (quot -11 -3)

Slides: The sum-of-first function

(define sum-of-first
  (lambda (n)
    (if (= n 0)
        0
        (+ (sum-of-first (- n 1)) n))))

> (sum-of-first 4)
> (sum-of-first 5)
     
Slides: The num-digits function

(define num-digits
  (lambda (n)
    (if (< n 10)
        1
        (+ 1 (num-digits (quotient n 10))))))

> (num-digits 59274)
> (num-digits 81)