[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>