在 Racket 中将结构递归转化为累积递归 [英] Turning structural recursion into accumulative recursion in Racket

问题描述

我有一些代码可以找到最大高度并将其替换为关联的名称.高度和名称有单独的列表，每个列表的长度相同且非空.

我可以使用结构递归来解决这个问题，但必须将其更改为累积式，我不确定如何做到这一点.我看到的所有例子都让我感到困惑.有人可以使用累积递归将代码合二为一吗?

(定义(最高的名字高度)(条件[(空?名字)高度][(> (第一高度) (第一(静止高度)))(缺点(名字)(最高(休息(休息名称))(休息(休息高度))))][else(最高(其余名称)(其余高度))]))

解决方案

首先，您提供的 tallest 函数实际上不起作用(调用 (tallest '(Bernie Raj Amy)(list 1.5 1.6 1.7)) 因合同错误而失败)，但我明白你在说什么.结构递归和累积递归有什么区别?

<小时>

好吧，结构递归的工作原理是构建一个 结构 作为返回值，其中该结构中的值之一是对同一函数的递归调用的结果.以阶乘的递归计算为例.你可以这样定义:

(定义(阶乘n)(如果(零?n)1(* n (阶乘 (sub1 n)))))

可视化该程序如何在输入 4 时执行.每次调用都会在乘法表达式中留下一个洞"，由递归子调用的结果填充.这是使用 _ 表示这些洞"之一的可视化效果.

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

请注意大部分工作是如何仅在达到最终情况后才完成的.大部分工作必须在调用返回时从堆栈中弹出的过程中完成，因为每次调用都依赖于对其子调用的结果执行一些额外的操作.

<小时>

累积递归有何不同?好吧，在累积递归中，我们对称为 accumulator 的函数使用了一个额外的参数.重写上述阶乘函数以使用累加器将使其看起来像这样:

(define (factorial n acc)(如果(零?n)acc(阶乘 (sub1 n) (* acc n))))

现在，如果我们想找到 4 的阶乘，我们必须调用 (factorial 4 1)，为累加器提供一个起始值(我将在片刻).如果你现在考虑调用堆栈，它看起来会大不相同.

注意没有要填充的漏洞"——factorial 函数的结果要么是累加器，要么是对自身的直接调用.这称为尾调用，对factorial的递归调用称为位于尾位置.

事实证明这很有帮助，原因有几个.首先，有些函数用累积递归更容易表达，尽管 factorial 可能不是其中之一.然而，更重要的是，Scheme 要求实现提供适当的尾调用(有时也称为尾调用优化")，这意味着进行尾调用时调用堆栈不会增加深度.>

关于尾调用如何工作以及它们为什么有用的现有信息有很多，所以我不会在这里重复.重要的是要理解 accumulative 递归涉及一个 accumulator 参数，这通常会导致使用尾调用实现结果函数.

但是我们如何处理额外的参数呢?好吧，我们实际上可以创建一个辅助"函数来执行累积递归，但我们将提供一个自动填充基本情况的函数.

(定义(阶乘n)(定义 (factorial-helper n acc)(如果(零?n)acc(factorial-helper (sub1 n) (* acc n))))(factorial-helper n 1))

这种习惯用法很常见，以至于 Racket 提供了一个named let"形式，将上述功能简化为:

(定义(阶乘n)(let helper ([n n] [acc 1])(如果(零?n)acc(helper (sub1 n) (* acc n))))))

但这只是同一想法的一些语法糖.

<小时>

好的，那么:这些如何适用于您的问题?嗯，实际上，使用累积递归可以很容易地实现你的问题.以下是您如何构建算法的细分:

1. 就像在原始示例中一样，您将遍历列表直到获得 empty.这将构成您的基本案例".
2. 您的累加器很简单——它将是您找到的当前最大元素.
3. 在每次迭代时，如果您发现一个元素大于当前最大值，则该元素成为新的累加器.否则，累加器保持不变.

将所有这些放在一起，这是一个简单的实现:

(define (tallest-helper names heights current-tallest)(条件[(空?名字)(汽车目前最高)][(> (第一高度) (cdr 当前最高))(tallest-helper (rest name) (rest heights)(缺点(名字)(第一高度)))][别的(tallest-helper (rest name) (rest heights)当前最高)]))

这可以通过多种方式进一步改进——将其包装在一个提供累加器起始值的函数中、使用命名的 let、删除一些重复等——但我会离开这对你来说是一个练习.

请记住:累加器实际上是您的工作总和".这是你的运行总数".明白这一点，事情就应该说得通.

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))]))

解决方案

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.

这篇关于在 Racket 中将结构递归转化为累积递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！