Hailperin, Chapter 3

Slides, Tail recursion

Slides, Not tail recursion

Slides, factorial and factorial-product

(define factorial
  (lambda (n)
    (factorial-product 1 n)))

(define factorial-product
  (lambda (a b)  ; Returns a*b!, b >= 0.
    (if (= b 0)
        a
        (factorial-product (* a b) (- b 1)))))

> (factorial 5)

Slides, Prove factorial-product is correct

Slides, Function power

(define power
 (lambda (b e) ; b raised to the power e
   (power-product 1 b e)))

(define power-product
 (lambda (a b e) ; a * b to the e power, e >= 0
   (if (= e 0)
       a
       (power-product (* a b) b (- e 1)))))

Slide, Exponentiation is not associative

Slides, Fermat numbers

(define fermat-number
  (lambda (n)
    (+ (repeatedly-square 2 n) 1)))

(define repeatedly-square
  (lambda (b n)
    (if (= n 0)
        b
        (repeatedly-square (* b b) (- n 1)))))

> (fermat-number 3)
> (fermat-number 5)

Notes:
repeatedly-square is tail recursive.

Pierre de Fermat thought that all Fermat numbers are prime.
F_0, F_1, F_2, F_3, and F_4 are all prime.
Euler discovered that F_5 equals (641)(6700417), and so is not prime.
No one knows if there is any other F_n that is prime for n > 5.

Demo
> (remainder 16 3)
> (remainder 17 3)
> (remainder 18 3)

Write (divides? a b), which returns true when a divides b evenly.

(define divides?
  (lambda (a b) ; Returns #t if a divides b evenly.
    (= (remainder b a) 0)))

> (divides? 3 15)
> (divides? 15 3)

Slides, Perfect numbers

Slide, Assuming sum-of-divisors, write perfect?

(define perfect?
  (lambda (n)
    (= (sum-of-divisors n) (* 2 n))))

Slides, sum-of-divisors

(define sum-of-divisors
  (lambda (n)
    (define sum-from-plus ; sum of all divisors of n which are
      (lambda (low addend) ; >= low, plus addend
        (if (> low n)
            addend    ; no divisors of n are greater than n
            (sum-from-plus (+ low 1) 
                           (if (divides? low n)
                               (+ addend low)
                               addend)))))
    (sum-from-plus 1 0)))

Is sum-from-plus tail recursive? Yes

> (perfect? 4)
> (perfect? 5)
> (perfect? 6)
> (perfect? 7)
> (perfect? 8)
...

What is the first perfect number after 6?

(define first-perfect-after
  (lambda (n)
    (if (perfect? (+ n 1))
        (+ n 1)
        (first-perfect-after (+ n 1)))))
        
Is first-perfect-after tail recursive? yes

> (first-perfect-after 0)
6
> (first-perfect-after 6)
28
> (first-perfect-after 28)
496
> (first-perfect-after 496)
8128

Note: the last one takes a while.


The let statement

> (let ((x 5) (y 6) (z 1))
    (+ x y z))
12

Rewrite first-perfect-after saving (+ n 1) with let

(define first-perfect-after-2
  (lambda (n)
    (let ((next (+ n 1)))
      (if (perfect? next)
          next
          (first-perfect-after-2 next)))))

Slide, Hallmarks of pure functional programming

Is let an assignment statement?

No. Once next is defined, there is no way to go back and change its value.

Slides, The Golden Ratio

(define phi
  (lambda (n)
    (if (= n 0)
        1
        (+ 1 (/ 1 (phi (- n 1)))))))

> (phi 0)
> (phi 1)
> (phi 2)
> (* (phi 2) 1.0)
> (* (phi 20) 1.0)
> (* (phi 21) 1.0)

Slides, The Josephus Problem

The text does the base case for you.