函数式编程——大量强调递归，为什么？

纯函数式编程意味着没有副作用的编程。这意味着，如果你写一个循环，你的循环体不能产生副作用。因此，如果您希望您的循环执行某些操作，那么它必须重用前一次迭代的结果，并为下一次迭代生成某些内容。因此，循环体是一个函数，它以前一次执行的结果作为参数，并使用自己的结果调用下一次迭代。与直接为循环编写递归函数相比，这并没有很大的优势。

一个不做琐碎事情的程序将不得不在某个点上迭代某些事情。对于函数式编程，这意味着程序必须使用递归函数。

丘奇 · 图灵的论文强调了不同可计算性模型之间的等价性。

我认为函数式编程有两个基本属性:

1. 函数是第一类成员(只有相关的，因为要使其有用，需要第二个属性)

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

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

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

如果你违反了第二条原则。传递函数(原则1)变得非常危险，因为现在函数的结果可能取决于调用函数的时间和频率。

递归没有什么特别的。它是编程和数学中广泛使用的工具，仅此而已。然而，函数式语言通常是极简主义的。它们确实引入了许多奇特的概念，比如模式匹配、类型系统、列表内涵等等，但它只不过是用于非常普通、非常强大、但又简单和原始的工具的语法糖。这些工具包括: 函数抽象和函数应用。这是有意识的选择，因为语言核心的简单性使得推理变得更加容易。它还使编写编译器更加容易。用这些工具来描述循环的唯一方法是使用递归，因此命令式程序员可能会认为函数式编程与递归有关。它不是，它只是需要模仿那些不能在 goto语句上丢弃这个语法糖的可怜的循环，因此它是他们坚持的第一件事情之一。

另一个需要递归的地方(可能是间接的)是处理递归定义的数据结构。最常见的例子是 list ADT。在 FP 中，它通常被定义为这样的 data List a = Nil | Branch a (List a)。因为这里的 ADT 定义是递归的，所以它的处理函数也应该是递归的。再次强调，递归在这里并不特殊: 在命令式语言和函数式语言中，以递归方式处理这样的 ADT 看起来很自然。那么，在列表式的 ADT 命令循环仍然可以采用，但在不同的树形结构的情况下，他们不能。

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

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

带来递归操作 规定的特性是不可变变量。

考虑一个用于计算列表和的简单函数(伪代码) :

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

尽管如此，在每次运行 lambda 时，sum变量的值必须改变。这在具有不可变变量的语言中是非法的，所以你必须以一种不会使状态发生变化的方式重写它:

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 中获得尾部调用优化。

递归用于处理归纳定义的数据，归纳定义的数据无处不在。

length (x:xs) = 1 + length xs

length [] = 0

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

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