(define (ssum n) (if (= n 1) 1 (+ (sqrt n) (ssum (- n 1)))))It works nicely and all, but it really takes some time to compute something like (ssum 1000000). In fact it pretty much bogs the interpreter down. It bogs the whole machine down. Is this necessary? Why is it happening? Well, it turns out that the problem is that this program takes up a lot of memory. But wait a second? Why is that? Looking at the program it isn't clear how it could take more than constant memory since there are no lists. However, this program is recursive, and each recursive call results in a new function record being pushed onto the call stack. This takes up a lot of space when there are 1,000,000 recursive calls, like there are in (ssum 1000000). This is the dark side of functional programming. There's a hidden penalty for all the convenience (yes, I said "convenience") of programming everything recursively, and that's the memory overhead.
However, there are certain recursive functions that don't require this memory overhead. For example, consider the following alternate definition of ssum:
(define (ssum-tr n e) (if (= n 0) e (ssum-tr (- n 1) (+ (sqrt n) e))))Note: The second paramter e must be zero in the initial call. The idea behind this function is that e carries arround the "extra" stuff you've already computed. Suppose you were computing
√1 + √2 + √3 + √4i.e. (ssum-tr 4 0). In computing this with ssum-tr you'd end up at some point with a recursive call (ssum-tr 2 3.73) which would indicate that the answer is ssum(4) = ssum(2) + 3.73, i.e.
ssum(2) = √1 + √2 + √3 + √4 = 6.15
\_____/ \_____/
= ssum(2) + 3.732 = 2.414 + 3.732 = 6.15
It's a different way of arriving at the same result.
However, lets watch the call stack evolve during
ssum-tr's computation of (ssum-tr 4 0):
n=0,e=6.15 ---> Answer!
n=1,e=5.15 n=1,e=5.15
n=2,e=3.73 n=2,e=3.73 n=2,e=3.73
n=3,e=2 n=3,e=2 n=3,e=2 n=3,e=2
n=4,e=0 n=4,e=0 n=4,e=0 n=4,e=0 n=4,e=0
------- ------- ------- ------- -------
Stack Stack Stack Stack Stack
Hopefully what you see is that there's no reason to remember
anything beyond the top record on the stack. We have the
answer without ever having to do a pop, and if we don't need
to do any pops, we didn't need to remember the stuff in the
first place. A function like this is called tail recursive.
Definition: A function is tail recursive if its output expression in every recursive case is only the recursive call.In Scheme, this means that the recursive call is outermost. In C/C++/Java, a tail-recursive function can be identified by looking at the
return statement(s) for the
recursive case(s): if the recursive call itself is the
outermost expression in the return, the function
is tail-recursive. The fundamental idea is that the result
returned by the recursive call is the answer; nothing else
needs to be done with it. In that case, there's no reason to
pop records off the stack of recursive calls, and if you're
never going to pop them off, they needn't be pushed in the
first place.
The function (define (ssum n) (if (= n 1) 1 (+ (sqrt n) (ssum (- n 1)))))
is not tail recursive because the output expression in the recursive
case is (+ (sqrt n) (ssum (- n 1))), which while
it contains a recursive call is not just a
recursive call. In constrast, the recursive case of ssum-tr
has output expression
(ssum-tr (- n 1) (+ (sqrt n) e)) which
is just a recursive call.
As we noted above, with tail recursive functions we could
actually forget about the stack and only ever remember what
would ordinarily be the top record of the stack. Thus, tail
recursive functions can be optimized to take less memory -
and usually to run faster as well. Scheme interpreters are
required to make this optimization whenever
functions are defined tail-recursively.
Our tail recursive ssum-tr has no trouble computing
(ssum-tr 1000000 0) .
-
Implement the
cos-minfunction tail-recursively (call itcos-min-tr), where(cos-min i j)whould return the integer in the range [i,j] with the smallest cosine. Here's a regular (non-tail) recursive solution:(define (cos-min i j) (if (= i j) j (let ((k (cos-min (+ i 1) j))) (if (< (cos i) (cos k)) i k))))Try it on the range 1 to 10,000,000. Takes a while, eh? Now do it with tail-recursion!
-
The inverse tangent of x, if -1 < x < 1, is
x - x^3/3 + x^5/5 - x^7/7 + x^9/9 - x^11/11 + ...
Write a function (inv-tan x i) that approximates
the inverse tangent of x using i terms of the above
sequence.
Write it normally first (inv-tan), then make it tail-recursive (inv-tan-tr)!
With 1000 terms, the answer should be about 0.7851481634599485
In a nutshell, consider the following:
(define L1 '(1 2 3)) (define L2 (cons 'a L1)) (define L3 (append '(8 9) L2))The second line creates a new list
(a 1 2 3) and
gives it the name L2. It hasn't modified
L1 in any way, so it's not like pushing a new
element on top of the stack which, of course, modifies the stack.
Since we have two distinct lists (1 2 3) and
(a 1 2 3), it would seem that the interpreter
would've created 7 list nodes. However, recall that we have
referential transparency, i.e. nothing is ever modified.
Therefore, there's no harm done if the linked lists that
store L2 and L1 share nodes. Same goes for L3.
In fact, internally, these three lists with a total of 13 data
values are represented internally by 6 nodes:
This means that (cdr L) and (cons x L) are
constant time operations (make sure you see why), i.e. they
take the same amount of time regardless of the size of
L. How about (append L1 L2)?
How does its running time depend on the length of
L1 and the length of L2? Think
carefully about this and make sure you know the answer!
This sharing of nodes has an important consequence: When
the name L1 goes out of scope, the interpreter
can't necessarily reclaim its nodes. Indeed, in this
example, if L2 or L3 are still in
scope, none of L1's nodes can be reclaimed.
What if L3 goes out of scope? Then the first
two nodes can be reclaimed, but not the rest. In general,
when this sharing of nodes occurs it becomes very difficult
to determine which nodes can be reclaimed. It's completely
impractical to expect the programmer to do it, and really
undesireable too, since Scheme programmers are supposed to
think of lists abstractly, and not bother with the details
of how the interpreter implements them. Thus, Scheme really
requires automatic garbage collection, meaning that the
interpreter has to figure out which nodes can be reclaimed.
(pair-with x L) is an
interesting one.
(define (pair-with x L) (map (lambda (i) (list x i)) L))Why? Because pair-with includes a lambda expression that defines a different function each time pair-with is called: Each time
pair-with is called with a different
x value, the function created by that
lambda-expression is different. So here's an example of
a function that creates new functions dynamically.
To really be able to create any function on-the-fly with a
lambda expression, we need some way to define recursive
functions in lambda expressions.
With what we've seen so far that's not possible, because we
have no name to use for the function in the recursive call.
Scheme's solution to this is a special variant of
let
called letrec. In a normal let you can't use a
name from the name-value list inside the name value list.
In letrec, you can use a name from any point after its first
appearance. The following expression evaluates to
a factorial function:
(letrec ( (f (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))) ) f)This is a nice way of creating tail-recursive function definitions without lots of named helper-functions. For example, this definition of
(power x k) is nice
and efficiently implemented with tail-recursion:
(define (power x k)
(letrec ((pow (lambda (exp c) (if (= exp 0) c (pow (- exp 1) (* x c))))))
(pow k 1)))