74

我开始了解函数式编程 [FP]（使用 Scala）。从我最初的学习中得出的一件事是 FP 严重依赖递归。而且看起来，在纯FP 中，进行迭代的唯一方法是编写递归函数。

由于递归的大量使用，FPs 不得不担心的下一件事情StackoverflowExceptions通常是由于长时间的递归调用。@tailrec这是通过引入一些优化来解决的（从 Scala v2.8 开始，在堆栈帧和注释的维护中与尾递归相关的优化）

有人可以告诉我为什么递归对函数式编程范式如此重要吗？如果我们迭代地做一些事情，函数式编程语言的规范中是否有一些东西会被“违反”？如果是，那么我也很想知道这一点。

PS：请注意，我是函数式编程的新手，所以如果他们解释/回答我的问题，请随时向我指出现有资源。此外，我确实理解 Scala 也特别提供了对迭代工作的支持。

4

9 回答 9

54

Church Turing 论文强调了不同可计算性模型之间的等价性。

使用递归，我们在解决某些问题时不需要可变状态，这使得用更简单的术语指定语义成为可能。因此，从形式上讲，解决方案可以更简单。

我认为 Prolog 比函数式语言更好地展示了递归的有效性（它没有迭代），以及我们在使用它时遇到的实际限制。

于 2012-09-30T08:07:39.703 回答
41

纯函数式编程意味着没有副作用的编程。这意味着，例如，如果您编写一个循环，则循环的主体不会产生副作用。因此，如果你想让你的循环做某事，它必须重用上一次迭代的结果并为下一次迭代产生一些东西。因此，您的循环体是一个函数，将先前执行的结果作为参数，并使用自己的结果调用自身以进行下一次迭代。与直接为循环编写递归函数相比，这并没有太大的优势。

一个不做一些微不足道的事情的程序将不得不在某个时候迭代某些事情。对于函数式编程，这意味着程序必须使用递归函数。

于 2012-09-30T08:03:49.047 回答
25

带来递归执行需求的特性是不可变变量。

考虑一个用于计算列表总和的简单函数（在伪代码中）：

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

现在，element列表的每次迭代都不同，但我们可以重写它以使用foreach带有 lambda 参数的函数来解决这个问题：

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

尽管如此，sum变量的值必须在每次运行 lambda 时更改。这在具有不可变变量的语言中是非法的，因此您必须以不改变状态的方式重写它：

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

现在，这个实现将需要大量地推入和弹出调用堆栈，并且所有小操作都会执行此操作的程序不会运行得很快。因此，我们将其重写为尾递归，这样编译器就可以进行尾调用优化：

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

当然，如果你想无限循环，你绝对需要一个尾递归调用，否则它会堆栈溢出。

Scala 中的@tailrec注解是帮助您分析哪些函数是尾递归的工具。您声称“此函数是尾递归的”，然后编译器会告诉您您是否弄错了。与其他函数式语言相比，这在 Scala 中尤其重要，因为运行它的机器 JVM 不能很好地支持尾调用优化，因此在所有相同的情况下，不可能在 Scala 中进行尾调用优化它在其他功能语言中。

于 2012-09-30T08:50:09.013 回答
8

TL;DR：递归用于处理无处不在的归纳定义数据。

当您在更高级别的抽象上操作时，递归是自然的。函数式编程不仅仅是用函数编码；它是关于在更高级别的抽象上操作，您自然会使用函数。使用函数，从任何有意义的上下文中重用相同的函数（再次调用它）是很自然的。

世界是通过重复相似/相同的构建块来构建的。如果你把一块布料切成两半，你就有两块布料。数学归纳法是数学的核心。我们，人类，计数（如，1,2,3...）。根据定义/构造该事物的相同情况，任何归纳定义的事物（例如{1} 中的数字是 {1和2}中的数字）都可以自然地由递归函数处理/分析。

递归无处不在。无论如何，任何迭代循环都是变相的递归，因为当你重新进入那个循环时，你又重新进入了同一个循环（只是可能有不同的循环变量）。因此，这不像发明有关计算的新概念，更像是发现基础并使其明确。

因此，递归是自然的。我们只是写下一些关于我们的问题的定律，一些涉及我们正在定义的函数的方程，它们保留了一些不变量（假设函数是连贯定义的），用简化的术语重新指定问题，瞧！我们有解决方案。

一个例子，一个计算列表长度的函数（一种归纳定义的递归数据类型）。假设它已定义，并返回列表的长度，这并不奇怪。它必须遵守哪些法律？在问题的何种简化下保留了哪些不变量？

最直接的是将列表拆分为其头元素，其余部分 - 即列表的尾部（根据列表的定义/构造方式）。法律是，

length (x:xs) = 1 + length xs

啊！但是空列表呢？一定是这样

length [] = 0

那么我们如何编写这样的函数呢？……等等……我们已经写好了！（在 Haskell 中，如果你想知道，函数应用是通过并列表达的，括号仅用于分组，并且(x:xs)是一个列表，其中包含x第一个元素，xs其余元素）。

允许这种编程风格的语言所需要的只是它具有TCO（也许有点奢侈， TRMCO），所以没有堆栈爆炸，我们已经准备好了。

另一件事是纯度 - 代码变量和/或数据结构（记录的字段等）的不变性。

这样做的作用是，除了让我们的大脑不必跟踪何时发生变化之外，它是否使时间在我们的代码中明确显示，而不是隐藏在我们“变化”的可变变量/数据中。从现在开始，我们只能在命令式代码中“改变”变量的值——过去我们不能很好地改变它的值，不是吗？

因此，我们最终得到了记录的更改历史列表，更改在代码中明确显示：而不是x := x + 2我们编写let x2 = x1 + 2. 它使推理代码变得容易得多。

为了使用TCOlength解决尾递归上下文中的不变性，请考虑在累加器参数范式下对上述函数的尾递归重写：

length xs = length2 0 xs              -- the invariant: 
length2 a []     = a                  --     1st arg plus
length2 a (x:xs) = length2 (a+1) xs   --     the length of 2nd arg

这里的 TCO 意味着调用帧重用，除了直接跳转，因此调用链length [1,2,3]实际上可以看作是改变了调用堆栈帧对应于函数参数的条目：

length [1,2,3]
length2 0 [1,2,3]       -- a=0  (x:xs)=[1,2,3]
length2 1 [2,3]         -- a=1  (x:xs)=[2,3]
length2 2 [3]           -- a=2  (x:xs)=[3]
length2 3 []            -- a=3  (x:xs)=[]
3

在纯语言中，没有任何值变异原语，表达变化的唯一方法是将更新的值作为参数传递给函数，以便进一步处理。如果进一步的处理与以前相同，那么自然我们必须为此调用相同的函数，将更新的值作为参数传递给它。这就是递归。

以下是计算参数列表长度的整个历史（如果需要，可以重用）：

length xs = last results
  where
     results = length3 0 xs
     length3 a []     = [a]
     length3 a (x:xs) = a : length3 (a+1) xs

在 Haskell 中，这被称为受保护的递归或核心递归（至少我认为是这样）。

于 2012-09-30T15:24:22.633 回答
6

递归没有什么“特别的”。它是编程和数学中广泛使用的工具，仅此而已。然而，函数式语言通常是极简主义的。它们确实引入了许多花哨的概念，如模式匹配、类型系统、列表理解等，但它只不过是非常通用和非常强大但简单和原始工具的语法糖。这些工具是：函数抽象和函数应用。这是有意识的选择，因为语言核心的简单性使得推理变得更加容易。它还使编写编译器更容易。用这种工具来描述循环的唯一方法是使用递归，因此命令式程序员可能会认为，函数式编程是关于递归的。它不是，goto声明，所以这是他们坚持的第一件事。

需要（可能是间接的）递归的另一点是处理递归定义的数据结构。最常见的例子是listADT。在 FP 中，它通常是这样定义的data List a = Nil | Branch a (List a)。由于这里ADT的定义是递归的，它的处理函数也应该是递归的。同样，这里的递归并不特别：以递归方式处理此类 ADT 在命令式和函数式语言中看起来都很自然。好吧，在类似列表的 ADT 命令式循环的情况下，仍然可以采用，但在不同的树状结构的情况下，它们不能。

所以递归没有什么特别之处。它只是另一种类型的功能应用程序。然而，由于现代计算系统的限制（来自 C 语言中糟糕的设计决策，这是事实上的标准跨平台汇编程序）函数调用不能无限嵌套，即使它们是尾调用。正因为如此，函数式编程语言的设计者要么将允许的尾调用限制为尾递归 (scala)，要么使用复杂的技术，如践踏（旧 ghc 代码生成）或直接编译为 asm（现代 ghc 代码生成）。

TL;DR：FP 中的递归没有什么特别之处，至少在 IP 中没有什么特别之处，但是，由于 JVM 的限制，尾递归是 scala 中唯一允许的尾调用类型。

于 2012-09-30T08:49:52.800 回答
6

我认为有两个属性对函数式编程至关重要：

  1. 函数是第一类成员（仅相关，因为要使其有用，需要第二个属性）

  2. 函数是纯函数，即使用相同参数调用的函数返回相同的值。

现在，如果您以命令式编程，则必须使用赋值。

考虑一个 for 循环。它有一个索引，并且在每次迭代中，索引都有不同的值。所以你可以定义一个返回这个索引的函数。如果您两次调用该函数，您可能会得到不同的结果。从而打破了第 2 条原则。

如果你违反了原则 2。传递函数（原则 1）会变得非常危险，因为现在函数的结果可能取决于函数被调用的时间和频率。

于 2012-09-30T08:33:01.190 回答
6

避免副作用是函数式编程的支柱之一（另一个是使用高阶函数）。

想象一下如何在不依赖突变的情况下使用命令式流控制。可能吗？

当然for (var i = 0; i < 10; i++) ...取决于突变（i++）。事实上，任何条件循环结构都可以。在while (something) ...将something取决于一些可变状态。当然，while (true) ...不使用突变。但是，如果您想退出该循环，则需要一个if (something) break. 确实，尝试考虑一种（非无限）循环机制，而不是不依赖于突变的递归。

怎么样for (var x in someCollection) ...？现在我们离函数式编程越来越近了。x可以认为是循环体的参数。重用名称与重新分配值不同。也许在循环体中，您将值作为（无突变）yield return的表达式。x

完全等效地，您可以将for循环体移动到函数体中foo (x) ...，然后someCollection使用高阶函数将其映射到上面 - 将循环构造替换为Map(foo, someCollection).

但是那么库函数是如何在Map没有变异的情况下实现的呢？好吧，当然使用递归！它已经为你完成了。一旦你开始使用第二个高阶函数来替换你的循环结构，就不再需要自己实现递归函数了。

此外，通过尾调用优化，递归定义等效于迭代过程。您可能还会喜欢这篇博文：http: //blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

于 2012-09-30T16:54:53.543 回答
2

上次我使用函数式语言（Clojure）时，我什至从未想过使用递归。一切都可以作为一组事物来处理，对它应用一个函数来获得零件产品，对其应用另一个函数，直到达到最终结果。

递归只是处理通常必须处理的多个项目的一种方式，而且不一定是最清晰的方式，以处理任何 g

于 2012-10-04T23:27:25.663 回答
1

为了新的 FP 学习者，我想加我的 2 美分。正如一些答案中提到的，递归是他们利用不可变变量但为什么我们需要这样做？这是因为它可以轻松地在多个内核上并行运行程序，但我们为什么要这样做呢？我们不能在单核中运行它并像往常一样快乐吗？不，因为要处理的内容每天都在增加，而且 CPU 时钟周期不能比添加更多内核显着增加。在过去的十年中，消费类计算机的时钟速度一直在 2.7 ghz 到 3.0 ghz 左右，而芯片设计人员在安装越来越多的晶体管时遇到了问题。而且 FP 长期以来一直是他们的，但没有

于 2016-03-26T16:40:23.863 回答