Turning structural recursion into accumulative rec

问题:

I have some code to find the maximum height and replace it with the associated name. There are separate lists for height and names, each the same length and non-empty.

I can solve this using structural recursion but have to change it into accumulative, and I am unsure how to do that. All the examples I have seen are confusing me. Is anybody able to turn the code into one using accumulative recursion?

(define (tallest names heights)
  (cond
    [(empty? names) heights]
    [(> (first heights) (first (rest heights)))
     (cons (first names) (tallest (rest (rest names)) (rest (rest heights))))]
    [else (tallest (rest names) (rest heights))]))

回答1:

First of all, your provided tallest function doesn't actually work (calling (tallest '(Bernie Raj Amy) (list 1.5 1.6 1.7)) fails with a contract error), but I see what you're getting at. What's the difference between structural recursion and accumulative recursion?

---

Well, structural recursion works by building a structure as a return value, in which one of the values inside that structure is the result of a recursive call to the same function. Take the recursive calculation of a factorial, for example. You might define it like this:

(define (factorial n)
  (if (zero? n) 1
      (* n (factorial (sub1 n)))))

Visualize how this program would execute for an input of, say, 4. Each call leaves a "hole" in the multiplication expression to be filled in by the result of a recursive subcall. Here's what that would look like, visualized, using _ to represent one of those "holes".

(* 4 _)
     (* 3 _)
          (* 2 _)
               (* 1 _)
                    1

Notice how a large portion of the work is done only after the final case is reached. Much of the work must be done in the process of popping the calls off the stack as they return because each call depends on performing some additional operation on its subcall's result.

---

How is accumulative recursion different? Well, in accumulative recursion, we use an extra argument to the function called an accumulator. Rewriting the above factorial function to use an accumulator would make it look like this:

(define (factorial n acc)
  (if (zero? n) acc
      (factorial (sub1 n) (* acc n))))

Now if we wanted to find the factorial of 4, we'd have to call (factorial 4 1), providing a starting value for the accumulator (I'll address how to avoid that in a moment). If you think about the call stack now, it would look quite different.

Notice how there are no "holes" to be filled in—the result of the factorial function is either the accumulator or a direct call to itself. This is referred to as a tail call, and the recursive call to factorial is referred to as being in tail position.

This turns out to be helpful for a few reasons. First of all, some functions are just easier to express with accumulative recursion, though factorial probably isn't one of them. More importantly, however, Scheme requires that implementations provide proper tails calls (sometimes also called "tail call optimization"), which means that the call stack will not grow in depth when tail calls are made.

There is plenty of existing information about how tail calls work and why they're useful, so I won't repeat that here. What's important to understand is that accumulative recursion involves an accumulator argument, which usually causes the resulting function to be implemented with a tail call.

But what do we do about the extra parameter? Well, we can actually just make a "helper" function that will do the accumulative recursion, but we will provide a function that automatically fills in the base case.

(define (factorial n)
  (define (factorial-helper n acc)
    (if (zero? n) acc
        (factorial-helper (sub1 n) (* acc n))))
  (factorial-helper n 1))

This sort of idiom is common enough that Racket provides a "named let" form, which simplifies the above function to this:

(define (factorial n)
  (let helper ([n n] [acc 1])
    (if (zero? n) acc
        (helper (sub1 n) (* acc n)))))

But that's just some syntactic sugar for the same idea.

---

Okay, so: how does any of this apply to your question? Well, actually, using accumulative recursion makes implementing your problem quite easy. Here's a breakdown of how you'd structure the algorithm:

1. Just like in your original example, you'd iterate through the list until you get empty. This will form your "base case".
2. Your accumulator will be simple—it will be the current maximum element you've found.
3. Upon each iteration, if you find an element greater than the current maximum, that becomes the new accumulator. Otherwise, the accumulator remains the same.

Putting these all together, and here's a simple implementation:

(define (tallest-helper names heights current-tallest)
  (cond
    [(empty? names)
     (car current-tallest)]
    [(> (first heights) (cdr current-tallest))
     (tallest-helper (rest names) (rest heights)
                     (cons (first names) (first heights)))]
    [else
     (tallest-helper (rest names) (rest heights)
                     current-tallest)]))

This can be further improved in plenty of ways—wrapping it in a function that provides the accumulator's starting value, using named let, removing some of the repetition, etc.—but I'll leave that as an exercise for you.

Just remember: the accumulator is effectively your "working sum". It's your "running total". Understand that, and things should make sense.