在Racket中将结构递归转化为累积递归

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

我可以使用结构递归来解决这个问题，但必须将其更改为累积递归，而且我不确定如何做到这一点。我见过的所有例子都让我困惑。有人能够将代码变成使用累积递归的代码吗？

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

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

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

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

想象一下这个程序如何针对输入执行，例如：4。每次调用都会在乘法表达式中留下一个“洞”，以便由递归子调用的结果填充。这就是看起来的样子，可视化，使用_代表这些“洞”之一。

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

注意大部分工作是如何完成的仅在那之后最终情况已达成。大部分工作必须在调用返回时将其从堆栈中弹出的过程中完成，因为每个调用都依赖于对其子调用结果执行一些附加操作。

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

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

现在如果我们想求 4 的阶乘，我们必须调用(factorial 4 1)，为累加器提供一个起始值（稍后我将讨论如何避免这种情况）。如果您现在考虑一下调用堆栈，它看起来会完全不同。

请注意，没有“漏洞”需要填补——结果如下：factorial函数要么是累加器，要么是对其自身的直接调用。这被称为尾调用，以及递归调用factorial被称为处于尾部位置.

事实证明这很有帮助，原因有几个。首先，有些函数用累积递归更容易表达，但factorial可能不是其中之一。然而，更重要的是，Scheme 要求实现提供正确的尾部呼叫（有时也称为“尾部调用优化”），这意味着进行尾部调用时调用堆栈的深度不会增长。

关于尾部调用如何工作以及它们为何有用的现有信息有很多，因此我不会在这里重复。重要的是要理解累计递归涉及到累加器参数，这通常会导致结果函数通过尾部调用来实现。

但是对于额外的参数我们该怎么办呢？好吧，我们实际上可以创建一个“辅助”函数来执行累积递归，但我们将提供一个自动填充基本情况的函数。

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

这种习惯用法很常见，以至于 Racket 提供了一个“命名的let" 形式，将上面的函数简化为：

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

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

可以，然后呢：这些如何适用于你的问题？嗯，实际上，使用累积递归使解决问题变得非常容易。以下是如何构建算法的详细说明：

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

将这些放在一起，这是一个简单的实现：

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

这可以通过多种方式进一步改进 - 将其包装在提供累加器起始值的函数中，使用命名let、删除一些重复内容等等——但我会将其作为练习留给您。

请记住：累加器实际上是您的“工作总和”。这是您的“运行总计”。明白了这一点，事情就应该有意义了。