PowerPoint Presentation
Time and space complexity in functional programming
CS 345
Lecture 10
Functional programming
invites certain problems!
Recursion can cause…
Stack overflow!
Always passing data around as arguments to functions (instead of mutating it) leads to…
Copies, copies everywhere!
Only using recursive data structures (linked lists) leads to…
0(n) lookup times compared to O(1) lookup times in arrays!
Functional languages also offer
unique solutions to these problems
To the problem of stack overflow:
Tail call recursion, and
tail call optimization
To the problem of excessive data copying, and O(n) lookup times:
Persistent data structures
Recursion can be space inefficient
(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(*5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (*3 2)))
(* 5 (* 4 6))
(* 5 24)
120
Optimize by rewriting with an “accumulator”
(fact 5 1)
(fact 4 5)
(fact 3 20)
(fact 2 60)
(fact 1 120)
120
Tail recursive re-writes (can) always have this structure:
When you reach the base case, return the accumulator:
(define (func count acc)
(if (= count 1)
acc
The recursive case will always start with a recursive call to the function (avoid suspended operations):
(define (func count acc)
(if (= count 1)
acc
(func…
The next item in the recursion will always count down the recursions in one way (- count 1) or another (cdr ls):
(define (func count acc)
(if (= count 1)
acc
(func (- count 1)…
The last item in the recursion must be an evaluation that accumulates your desired total into the accumulator:
(define (func count acc)
(if (= count 1)
acc
(func (- count 1) (some-evaluation acc))
Avoid an awkward function signature
with an internal (i.e. nested) definition:
(fact 5 1)
(fact 4 5)
(fact 3 20)
(fact 2 60)
(fact 1 120)
120
Functional language compilers recognize tail recursion and re-use one stack frame for the tail call
“Tail recursion refers to the special case where the return value of the recursive branch is nothing more than the value of the next recursive call (tail call).”
TAIL CALL: (fact (- num 1) (* num acc))
How does a compiler recognize tail calls?
From the syntax of the function definition.
Non tail recursive:
(define (func ls)
(if (empty? ls)
0
(+ (car ls) (func (cdr ls)))))
Not tail recursive, because after the recursive branch returns, there is still something left to evaluate.
Tail recursive:
(define (func ls acc)
(if (empty? ls)
acc
(func (cdr ls) (+ acc (car ls)))))
Tail recursive, because no previous calls are left waiting for their arguments. The last recursive call is the last thing to evaluate.
Tail recursive or non tail recursive?
Non tail recursive
(define (g n)
(if (= n 1)
2
(+ (g (- n 1)) 3)))
Tail recursive or non tail recursive?
Tail recursive
(define (sum x y)
(if (= x 0)
y
(sum (- x 1) (+ y x))))
Tail recursive or non tail recursive?
Tail recursive
(define (all-pos ls)
(cond ((empty? ls) #t)
((negative? (car ls)) #f)
((positive? (car ls)) (all-pos (cdr ls)))))
Tail recursive or non tail recursive?
Tail recursive
(define (bar f base ls)
(if (empty? ls)
base
(bar f (f (car ls) base) (cdr ls))))
foldl left!
Tail recursive or non tail recursive?
Non tail recursive
(define (foo f base ls)
(if (empty? ls)
base
(f (car ls) (foo f base (cdr ls)))))
fold right!
Tail recursive version of repeated
Trace
((repeated add-one 2) 3)
((lambda (x) ((repeated add-one (- 2 1)) (add-one x))) 3)
((repeated add-one 1) (add-one 3))
((repeated add-one 1) 4)
((lambda (x) ((repeated add-one (- 1 1)) (add-one x))) 4)
((repeated add-one 0) (add-one 4))
((repeated add-one 0) 5)
((lambda (x) x) 5)
5
Compare
((repeated add-one 2) 3)
((lambda (x) (add-one ((repeated add-one 1) x))) 3)
(add-one ((repeated add-one 1) 3))
(add-one ((lambda (x) (add-one ((repeated add-one 0) x))) 3))
(add-one (add-one ((repeated add-one 0) 3)))
(add-one (add-one ((lambda(x) x) 3)))
(add-one (add-one 3))
(add-one 4)
5
Let’s do this one together
Let’s do this one together, too
A tail-recursive function that returns the maximum value in a list
(define (my-max ls)
(…
A tail-recursive function that returns the maximum value in a list
Participation Quiz
Write a function called find-pred:
(define (find-pred pred ls) …
Inside the body of find-pred, write a tail-recursive version of the function.
The “pred” should be something like < or > : in other words, a function that itself takes two arguments and returns a boolean.
If you call (find-pred > (list 4 6 3 9 2)), it should return 9.
If you call (find-pred < (list 4 6 3 9 2)), it should return 2. /docProps/thumbnail.jpeg