我有以下 Scala 片段。为了解决我给定的问题，我“作弊”了一点，并使用了var——本质上是一种非最终的、可变的数据类型。它的值在循环的每次迭代中更新。我花了很多时间试图弄清楚如何仅使用递归和不可变数据类型和列表来做到这一点。
原始片段：
def countChange_sort(money: Int, coins: List[Int]): Int =
if (coins.isEmpty || money < 0)
0
else if (coins.tail.isEmpty && money % coins.head != 0) {
0
} else if (coins.tail.isEmpty && money % coins.head == 0 || money == 0) {
1
} else {
-- redacted --
}
}
本质上，有什么基本的技术可以用来消除i，尤其是累积cnt变量？
谢谢！！
有很多不同的方法可以解决函数式的问题。通常，您以与设计命令式算法时不同的方式开始分析问题，因此编写命令式算法然后将其“转换”为函数式算法不会产生非常自然的函数式算法（而且您经常会错过功能风格的许多潜在好处）。但是，如果您是一位经验丰富的命令式程序员，刚开始使用函数式编程，那么您已经掌握了一切，这是开始了解新概念的好方法。因此，这里是您如何以一种相当没有创意的方式（即不提出不同的算法）将您编写的函数“转换”为函数样式的方法。
让我们只考虑else表达式，因为其余的都很好。
函数式风格没有循环，所以如果你需要多次运行一段代码（命令式循环的主体），那段代码必须是一个函数。通常该函数是一个简单的非递归函数，并且您调用诸如 map 或 fold 之类的高阶函数来执行实际递归，但我假设您需要练习递归思考并希望明确地看到它。循环条件是根据您在循环主体中手头的数量计算得出的，因此我们只需让循环替换函数根据完全相同的条件递归调用自身：
} else {
var cnt = 0
var i = 0
def loop(????) : ??? = {
if (money - (i * coins.head) > 0) {
cnt += countChange_sort(money - (i * coins.head), coins.tail)
i = i + 1
loop(????)
}
}
loop(????)
cnt
}
信息仅通过其输入参数或通过其定义传递给函数，并通过函数的返回值从函数传递。
在创建函数时（在编译时，或在创建闭包时的运行时），通过其定义进入函数的信息是恒定的。cnt对于and中包含的信息听起来不是很有用，i每次调用都需要不同。所以它们显然需要作为参数传入：
} else {
var cnt = 0
var i = 0
def loop(cnt : Int, i : Int) : ??? = {
if (money - (i * coins.head) > 0) {
cnt += countChange_sort(money - (i * coins.head), coins.tail)
i = i + 1
loop(cnt, i)
}
}
loop(cnt, i)
cnt
}
但是我们要使用cnt函数调用后的最终值。如果信息只通过 loop它的返回值传递，那么我们只能cnt通过loop返回它来获得最后一个值。这很容易：
} else {
var cnt = 0
var i = 0
def loop(cnt : Int, i : Int) : Int = {
if (money - (i * coins.head) > 0) {
cnt += countChange_sort(money - (i * coins.head), coins.tail)
i = i + 1
loop(cnt, i)
} else {
cnt
}
}
cnt = loop(cnt, i)
cnt
}
coins, money, 和countChange_sort是“通过定义进入函数”的信息示例。coins甚至money是“变量”，但在定义时它们是恒定的loop。如果你想loop从 of 的主体中移出countChange_sort成为一个独立的函数，你将不得不 makecoins和money额外的参数；它们将从顶级调用 incountChange_sort传入，然后在内部的每个递归调用中未经修改地传递loop。尽管如此，这仍然会loop依赖于countChange_sort自身（以及算术运算符*和-！），因此您永远不会真正摆脱让函数了解不会通过其参数进入它的外部事物。
看起来还不错。但是我们仍然在内部使用赋值语句loop，这是不对的。然而，我们所做的只是分配新值cnt，i然后将它们传递给 的递归调用loop，因此可以轻松删除这些分配：
} else {
var cnt = 0
var i = 0
def loop(cnt : Int, i : Int) : Int = {
if (money - (i * coins.head) > 0) {
loop(cnt + countChange_sort(money - (i * coins.head), coins.tail), i + 1)
} else {
cnt
}
}
cnt = loop(cnt, i)
cnt
}
现在有一些明显的简化，因为除了初始化它们，然后传递它们的初始值，分配给一次然后立即返回它之外，我们cnt并没有真正对可变对象做任何事情。所以我们可以（最终）完全摆脱可变的：icntcnti
} else {
def loop(cnt : Int, i : Int) : Int = {
if (money - (i * coins.head) > 0) {
loop(cnt + countChange_sort(money - (i * coins.head), coins.tail), i + 1)
} else {
cnt
}
}
loop(0, 0)
}
我们完成了！看不到副作用！
请注意，我根本没有考虑过您的算法实际上做了什么（我什至没有尝试弄清楚它是否真的正确，尽管我认为它是正确的）。我所做的只是直接应用了信息仅通过其参数进入函数并通过其返回值离开的一般原则。表达式可访问的所有可变状态实际上是表达式的额外隐藏输入和隐藏输出。使它们成为不可变的显式输入和输出，然后允许您修剪掉不需要的输入和输出。例如，i不需要包含在返回值中，loop因为它实际上并不是任何东西都需要的，因此转换为函数式样式已经清楚地表明它纯粹是内部的loop，而您必须实际阅读命令式版本的代码才能推断出这一点。
cnt并且i是所谓的累加器。累加器没有什么特别的，它们只是普通的参数；该术语仅指它们的使用方式。基本上，如果您的算法需要随时跟踪某些数据，您可以引入一个累加器参数，以便每个递归调用都可以“转发”到目前为止已经完成的数据。它们通常扮演局部临时可变变量在命令式算法中的角色。
一旦确定没有更多工作要做，递归函数的返回值就是累加器参数的值是很常见的模式，就像cnt在这种情况下发生的那样。
Note that these sort of techniques don't necessarily produce good functional code, but it's very easy to convert functions implemented using "local" mutable state to functional style using this technique. Pervasive non-local use of mutability, such as is typical of most traditional OO programs, is harder to convert like this; you can do it, but you tend to have to modify the entire program at once, and the resulting functions have large numbers of extra arguments (explicitly exposing all the hidden data-flow that was present in original program).
我没有任何基本技术可以专门更改您拥有的代码。但是，这里有一个解决递归算法的一般技巧：
你能把问题分解成子问题吗？例如，在金钱的例子中，如果你试图用 5 美元达到 10 美元，这类似于用 5 美元达到 5 美元的问题（已经选择了 5 美元一次）。试着画出来并制定规则。您会惊讶于您的解决方案明显正确得多。
由于没有人回答您的问题，我将尝试给您一些提示：什么是循环？遍历集合的每个元素。停止满足条件
你可以用递归做什么：遍历集合的每个元素。停止满足条件。
开始简单地编写一个没有 vars 的方法来打印集合的每个元素。然后剩下的就变得简单了，看看你的循环和你在做什么。无需直接操作变量（如 i=i + 1），只需将 i + 1 传递给您的方法的递归调用。
高温高压