# Contents

• Factorial
• Fibonacci
• Countdown
• Map
• Recursion "shapes"
• Tail call optimisation
• Iterative forms
• Discussion

# Factorial

```(define (fact n)
(if (= 0 n)
1
(* n (fact (- n 1)))))

> (fact 3)
6
> (fact 4)
24
> (fact 5)
120
```

# Fibonacci

```(define (fib n)
(if (<= n 2)
1
(+  (fib (- n 1))
(fib (- n 2)))))

> (fib 2)
1
> (fib 3)
2
> (fib 4)
5
> (fib 5)
8
```

# Countdown

```(define (countdown n)
(if (= n 0)
null
(begin
(display n)
(newline)
(countdown (- n 1)))))

> (countdown 4)
4
3
2
1
()
```

# Map

```

```
```(define (my-map fn lst)
(if (null? lst)
null
(cons (fn (car lst))
(my-map fn (cdr lst)))))

> (my-map abs (list 2 -3 4))
(2 3 4)
```

# Recursion "shapes" - fact

```(define (fact n)
(if (= 0 n)
1
(* n (fact (- n 1)))))

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
```

# Recursion "shapes" - fib

```(define (fib n)
(if (<= n 2)
1
(+  (fib (- n 1))
(fib (- n 2)))))

(fib 5)
(+ (fib 4) (fib 3))
(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))
(+ (+ (+ (fib 2) (fib 1)) 1) (+ 1 1))
(+ (+ (+ 1 1) 1) 2)
(+ (+ 2 1) 2)
(+ 3 2)
5
```

# Recursion "shapes" - countdown

```(define (countdown n)
(if (= n 0)
null
(begin (display n) (newline)
(countdown (- n 1)))))

(countdown 4)
(countdown 3)
(countdown 2)
(countdown 1)
(countdown 0)
()
```

# Tail call optimisation

• The previous stack frame is no longer needed
• Throw it away

# Recursion "shapes" - my-map

```(define (my-map fn lst)
(if (null? lst)
null
(cons (fn (car lst))
(my-map fn (cdr lst)))))

(my-map abs (list 2 -3 4))
(cons (abs 2) (mymap abs (list -3 4)))
(cons 2 (cons (abs -3) (mymap abs (list 4))))
(cons 2 (cons 3 (cons (abs 4) (my-map abs null))))
(cons 2 (cons 3 (cons 4 null)))
(cons 2 (cons 3 (list 4)))
(cons 2 (list 3 4))
(list 2 3 4)
```

# Iterative forms - fact

```(define (fact-it n)
(define (impl acc count)
(if (= 0 count)
acc
(impl (* count acc) (- count 1))))
(impl 1 n))

> (fact-it 3)
6
> (fact-it 4)
24
> (fact-it 5)
120
```

# Iterative forms - fact-it "shape"

```(define (fact-it n)
(define (impl acc count)
(if (= 0 count)
acc
(impl (* count acc) (- count 1))))
(impl 1 n))

(fact-it 3)
(impl 1 3)
(impl (* 3 1) (- 3 1))
(impl 3 2)
(impl (* 2 3) (- 2 1))
(impl 6 1)
(impl (* 1 6) (- 1 1))
(impl 6 0)
6
```

# Iterative forms (3) - fib

```(define (fib-it n)
(define (impl acc1 acc2 count)
(if (= count 2)
acc1
(impl (+ acc1 acc2) acc1 (- count 1))))
(impl 1 1 n))

> (fib-it 2)
1
> (fib-it 3)
2
> (fib-it 4)
3
> (fib-it 5)
5
```

# Iterative forms (4) - fib-it "shape"

```(define (fib-it n)
(define (impl acc1 acc2 count)
(if (= count 2)
acc1
(impl (+ acc1 acc2) acc1 (- count 1))))
(impl 1 1 n))

(fib-it 5)
(impl (+ 1 1) 1 (- 5 1))
(impl 2 1 4)
(impl (+ 2 1) 2 (- 4 1))
(impl 3 2 3)
(impl (+ 3 2) 3 (- 3 1))
(impl 5 3 2)
5
```

# Iterative form for map?

• No, but "Tail call optimisation modulo cons"