[racket] recursion?? two
On Jun 6, 2012, at 6:17 AM, Ronald Reynolds wrote:
> Is it correct to say that when I call a function inside of it's own definition I am just making it repeat loop?
> (define (my-map f lst)
> (cond
> [(empty? lst) empty]
> [else (cons (f (first lst))
> (my-map f (rest lst)))]))
> Is this code telling racket to repeat until lst is empty? Thx to all for your help.
In some cases, the effect is indeed similar to a repeat loop. But I find function calling to be simpler and easier to understand than loops, so I would rather think of it the other way around: when you write a repeat loop, you are really doing a particularly simple form of recursion. Any loop can be straightforwardly rewritten as a recursion, but many if not most examples of recursion CANNOT be straightforwardly rewritten as loops.
In other words, if you try to interpret every recursion as a loop, a lot of the examples simply won't fit into that mold. You're better off thinking of recursion as calling a helper function which (by pure coincidence) happens to solve the same problem as the original function.
Let's re-develop "my-map" in terms of helper functions. It's sometimes easier to solve a restricted version of a problem than the whole problem, so let's write a version that's only guaranteed to work on very short lists.
; my-map-0: does the same thing as my-map, but only guaranteed to work if lst is empty.
(define (my-map-0 f lst)
(cond [(empty? lst) empty]
[else (error 'my-map-0 "list too long")]))
Of course, that's not very useful, so let's write a version that works on SLIGHTLY longer lists.
; my-map-1: does the same thing as my-map, but only guaranteed to work if lst is at most one element.
(define (my-map-1 f lst)
(cond [(empty? lst) empty]
[else (cons (f (first lst)) (my-map-0 f (rest lst)))]))
; note that if lst is at most one element, then (rest lst) will be empty, so my-map-0 will work
; my-map-2: does th same thing as my-map, but only guaranteed to work if lst is at most two elements.
(define (my-map-2 f lst)
(cond [(empty? lst) empty]
[else (cons (f (first lst)) (my-map-1 f (rest lst)))]))
; note that if lst is at most two elements, then (rest lst) will be at most length 1, so my-map-1 will work
; my-map-3: does th same thing as my-map, but only guaranteed to work if lst is at most three elements.
(define (my-map-3 f lst)
(cond [(empty? lst) empty]
[else (cons (f (first lst)) (my-map-2 f (rest lst)))]))
; note that if lst is at most three elements, then (rest lst) will be at most length 2, so my-map-2 will work
And so on. No recursion, just a bunch of helper functions, each of which solves "the same" problem, but is guaranteed to work on a different subset of cases.
Obviously, my-map-1, my-map-2, and my-map-3 all look extremely similar, so it would make sense to parameterize:
; my-map-n : does the same thing as my-map, but only guaranteed to work if lst is at most n elements.
(define (my-map-n n f lst)
(cond [(empty? lst) empty]
[else (cons (f (first lst)) (my-map-n (- n 1) f (rest lst)))]))
Then we notice that we're not actually USING n anywhere, so we might as well leave it out:
(define (my-map f lst)
(cond [(empty? lst) empty]
[else (cons (f (first lst)) (my-map f (rest lst)))]))
Stephen Bloch
sbloch at adelphi.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120606/01715889/attachment-0001.html>