Tail-recursion: - the recursive call is the last operation performed in the procedure - can be optimized to avoid unnecessary stack space usage
TCO (Tail Call Optimization):
- eliminates the need to create new stack frames for each recursive call
- prevent stack overflow errors
Exercise 1.9: Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.
(define (+ a b)
(if (= a 0) b (inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0) b (+ (dec a) (inc b))))Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?
$ racket 1.9-inc-dec.rkt
>(add-1 4 5)
> (dec 4)
< 3
> (add-1 3 5)
> >(dec 3)
< <2
> >(add-1 2 5)
> > (dec 2)
< < 1
> > (add-1 1 5)
> > >(dec 1)
< < <0
> > >(add-1 0 5)
< < <5
> > (inc 5)
< < 6
> >(inc 6)
< <7
> (inc 7)
< 8
>(inc 8)
<9
9
>(add-2 4 5)
> (dec 4)
< 3
> (inc 5)
< 6
>(add-2 3 6)
> (dec 3)
< 2
> (inc 6)
< 7
>(add-2 2 7)
> (dec 2)
< 1
> (inc 7)
< 8
>(add-2 1 8)
> (dec 1)
< 0
> (inc 8)
< 9
>(add-2 0 9)
<9
9Tree recursion:
- can suffer from redundant computation
- potentially exponential time complexity
Exercise 1.11: A function f is defined by the rule that
f(n) = n if n < 3
f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3
Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
$ racket 1.11-f-recursive.rkt
x: 4
f(x): >(f 4)
> (f 3)
> >(f 2)
< <2
> >(f 1)
< <1
> >(f 0)
< <0
< 4
> (f 2)
< 2
> (f 1)
< 1
<11
11$ racket 1.11-f-iterative.rkt
x: 4
f(x): >(f 4)
>(f-iter 2 1 0 4)
>(f-iter 4 2 1 3)
>(f-iter 11 4 2 2)
>(f-iter 25 11 4 1)
>(f-iter 59 25 11 0)
<11
11- Growth rates: to measure that resource (time, space) required by an algorithm as the size of the input increases
- big O: express the upper bound of the growth rate
- Common growth rates classes: O(1), O (log n), O(n), O(n^2), O(2^n)