我正在学习函数式编程[FP](使用Scala)。从我最初的学习中可以看出，FP在很大程度上依赖递归。而且，在纯FP中，做迭代工作的唯一方法是编写递归函数。
由于递归的大量使用，FP接下来要担心的似乎是StackoverflowExceptions，这通常是由于长时间的递归调用。这是通过引入一些优化来解决的(从Scala v2.8开始，在堆栈帧和@tailrec注释的维护中与尾部递归相关的优化)
有人能告诉我为什么递归对函数式编程范式如此重要吗？如果我们迭代地做事，函数式编程语言的规范中是否有什么东西会被"违反"？如果是的话，那么我也很想知道这一点。
附言：请注意，我是函数式编程的新手，所以如果他们解释/回答我的问题，请随时向我介绍现有的资源。此外，我确实理解Scala特别为做迭代工作提供了支持。
Church Turing论文强调了不同可计算性模型之间的等价性。
使用递归，在解决某些问题时，我们不需要可变状态，这使得可以用更简单的术语指定语义。因此，从形式意义上讲，解决方案可以更简单。
我认为Prolog比函数式语言更好地展示了递归的有效性(它没有迭代)，以及我们在使用它时遇到的实际限制
纯函数式编程意味着无副作用的编程。这意味着，例如，如果你写一个循环，循环的主体不会产生副作用。因此，如果你想让你的循环做一些事情，它必须重用上一次迭代的结果，并为下一次迭代产生一些东西。因此，循环的主体是一个函数，将上一次执行的结果作为参数，并用自己的结果为下一次迭代调用自己。与直接为循环编写递归函数相比，这并没有太大的优势。
一个不做琐碎事情的程序将不得不在某个时刻迭代某些事情。对于函数式编程，这意味着程序必须使用递归函数。
产生递归执行要求的特性是不可变的变量。
考虑一个计算列表总和的简单函数(伪代码)：
fun calculateSum(list):
sum = 0
for each element in list: # dubious
sum = sum + element # impossible!
return sum
现在，列表的每次迭代中的element都是不同的，但我们可以重写它，使用带有lambda参数的foreach函数来解决这个问题：
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的尾调用优化不可能像在其他函数语言中一样。
TL；DR：递归用于处理归纳定义的数据，这些数据无处不在
当您在更高级别的抽象上操作时，递归是很自然的。函数式编程不仅仅是用函数进行编码；它是关于在更高级别的抽象上操作，在那里您自然地使用函数。使用函数，从任何有意义的上下文重用同一个函数(再次调用它)是很自然的。
世界是由相似/相同的构建块重复构建的。如果你把一块织物切成两半，你就得到了两块织物。数学归纳法是数学的核心。我们，人类，计数(如，1,2,3…)。任何归纳定义的事物(如，{来自1｝的数字是{1，来自2｝的数。)都可以自然地通过递归函数进行处理/分析，根据定义/构建该事物的相同情况。
递归无处不在。任何迭代循环都是伪装的递归，因为当你重新进入那个循环时，你会再次进入同一个循环(只是使用不同的循环变量)。因此，这不像发明关于计算的新概念，更像是发现的基础，并使其明确。
因此，递归是自然的。我们只是写下一些关于我们问题的定律，一些涉及我们定义的函数的方程，这些方程保持了一些不变(假设函数是一致定义的)，用简化的术语重新指定问题，瞧！我们有解决方案。
例如，一个计算列表长度的函数(一种归纳定义的递归数据类型)。假设它已定义，并返回列表的长度，这并不奇怪。它必须遵守哪些法律？在对问题进行何种简化的情况下，保留了什么不变量？
最直接的方法是将列表拆分为head元素，其余部分也就是列表的尾部(根据列表的定义/构造方式)。法律是，
length (x:xs) = 1 + length xs
嗯！但是空名单呢？肯定是
length [] = 0
那么我们如何编写这样一个函数呢？。。。等待我们已经写好了！(在Haskell中，如果您想知道函数应用程序是通过并置来表达的，括号只用于分组，而(x:xs)是一个列表，x是第一个元素，xs是其余元素)。
我们所需要的一种语言允许这种编程风格，就是它有TCO(也许，有点奢侈的TRMCO)，所以没有堆栈爆炸，我们已经做好了准备。
另一件事是代码变量和/或数据结构(记录的字段等)的纯度-不变性。
除了让我们的大脑不必追踪什么时候发生了变化之外，它还让时间在我们的代码中变得明显，而不是隐藏在我们的"时间"中；改变"；可变变量/数据。我们只能"；改变"；在命令式代码中，从现在起变量的值-我们过去不能很好地改变它的值，是吗？
因此，我们最终得到了记录的更改历史列表，代码中的更改非常明显：我们写的不是x := x + 2，而是let x2 = x1 + 2。它使关于代码的推理变得更加容易。
为了解决TCO尾部递归上下文中的不变性，考虑在累加器自变量范式下对上述函数length的尾部递归重写：
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中，这被称为保护递归，或者共诅咒(至少我认为是这样)。
我认为有两个属性对函数式编程至关重要：
-
函数是第一类成员(仅相关，因为要使其有用，需要第二个属性)
-
函数是纯函数，即使用相同参数调用的函数返回相同的值。
现在，如果您以命令式样式编程，则必须使用赋值。
考虑一个for循环。它有一个索引，每次迭代的索引都有不同的值。所以你可以定义一个函数来返回这个索引。如果您调用该函数两次，可能会得到不同的结果。从而打破了第二条原则。
如果你违反了第二条原则。传递函数(原则1)变得非常危险，因为现在函数的结果可能取决于函数何时以及多久被调用一次。
递归中没有任何"特殊"之处。它是编程和数学中广泛使用的工具，仅此而已。然而，函数式语言通常是极简主义的。它们确实引入了许多花哨的概念，如模式匹配、类型系统、列表理解等，但对于非常通用、非常强大、但简单原始的工具来说，这只不过是语法糖。这些工具是：函数抽象和函数应用。这是有意识的选择，因为语言核心的简单性使推理变得更加容易。它还使编写编译器变得更容易。用这种工具描述循环的唯一方法是使用递归，因此命令式程序员可能会认为，函数式编程是关于递归的。事实并非如此，只是需要为那些不能在goto语句上撒下语法糖的穷人模仿那些花哨的循环，所以这是他们最先陷入的问题之一。
需要(可能是间接的)递归的另一点是处理递归定义的数据结构。最常见的例子是listADT。在FP中，它通常是这样定义的data List a = Nil | Branch a (List a)。由于这里ADT的定义是递归的，所以它的处理函数也应该是递归的。同样，这里的递归并不是特别的：以递归方式处理这样的ADT在命令式语言和函数式语言中看起来都很自然。在类似列表的ADT的情况下，命令式循环仍然可以采用，但在不同的树状结构的情况下不能。
所以递归并没有什么特别之处。它只是另一种类型的函数应用程序。然而，由于现代计算系统的局限性(这源于C语言中糟糕的设计决策，C语言是事实上的标准跨平台汇编程序)，即使函数调用是尾部调用，也不能无限嵌套。因此，函数式编程语言的设计者必须将允许的尾部调用限制为尾部递归(scala)，或者使用复杂的技术，如蹦床(旧的ghc代码生成)或直接编译为asm(现代ghc代码生成器)。
TL；DR：FP中的递归没有什么特别之处，至少在IP中没有，但是，由于JVM的限制，尾递归是scala中唯一允许的尾调用类型。
避免副作用是函数编程的支柱之一(另一个是使用高阶函数)。
想象一下，在不依赖突变的情况下，如何使用命令流控制。有可能吗？
当然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是如何在没有突变的情况下实现的呢？当然，使用递归！这是为你做的。一旦开始使用高阶函数的第二个pilar来替换循环结构，就不那么常见了，必须自己实现递归函数。
此外，对于尾调用优化，递归定义等效于迭代过程。你可能还喜欢这篇博客文章：http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx
上次我使用函数式语言(Clojure)时，我甚至从未尝试过使用递归。所有的事情都可以作为一组事情来处理，一个函数被应用到其中以获得零件产品，另一个函数也被应用到其上，直到达到最终结果。
递归只是处理多个项目的一种方法，而不一定是最清晰的方法，您通常必须处理这些项目才能处理任何g
为了新的FP学习者，我想增加我的2美分。正如一些答案中提到的，递归是他们利用不可变变量的方法，但为什么我们需要这样做？这是因为它使得在多个内核上并行运行程序变得容易，但我们为什么要这样呢？难道我们不能像往常一样快乐地运行它吗？不，因为要处理的内容每天都在增加，CPU时钟周期的增加不可能比添加更多内核更显著。在过去的十年里，消费类计算机的时钟速度一直在2.7ghz到3.0ghz之间，芯片设计师在安装越来越多的晶体管时遇到了问题。同样，FP在很长一段时间以来一直是他们的专利，但由于它使用递归和内存在当时非常昂贵，所以没有普及，但随着时钟速度年复一年地飙升，社区决定继续使用OOP编辑：它很快，我只有几分钟的