Recursion in Scheme

Andy Balaam

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"

Discussion