F#尾递归,为什么不写while循环？

Question

我正在学习F#(一般来说是功能编程的新手,虽然多年来使用C#的功能方面,但让我们面对它,这是非常不同的)我读过的一件事是F#编译器识别尾递归并编译它进入一个while循环(参见http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/).

我不明白的是,为什么你会写一个递归函数而不是一个while循环,如果那就是它将会变成什么.特别是考虑到你需要做一些额外的工作来使你的函数递归.

我有一种感觉,有人可能会说while循环不是特别功能,你想要所有功能和诸如此类的东西,所以你使用递归,但那么为什么编译器将它变成while循环就足够了？

谁可以给我解释一下这个？

Answer 1

您可以对编译器执行的任何转换使用相同的参数.例如,当您使用C#时,您是否使用过lambda表达式或匿名委托？如果编译器只是将它们转换为类和(非匿名)委托,那么为什么不自己使用这些结构呢？同样,你有没有使用迭代器块？如果编译器只是将它们转换为显式实现的状态机IEnumerable<T>,那么为什么不自己编写代码呢？或者如果C#编译器无论如何都要发出IL,为什么还要首先编写C#而不是IL呢？等等.

所有这些问题的一个明显答案是我们想要编写代码,使我们能够清楚地表达自己.同样,有许多算法是自然递归的,因此编写递归函数通常会导致这些算法的清晰表达.特别是,在许多情况下,可以说更容易推理递归算法的终止而不是while循环(例如,是否存在明确的基本情况,并且每个递归调用是否使问题"更小"？).

但是,由于我们正在编写代码而不是数学论文,所以拥有满足某些实际性能标准的软件(例如处理大量输入而不会溢出堆栈的能力)也是很好的.因此,将尾递归转换为while循环的等价物这一事实对于能够使用递归的算法公式至关重要.

Answer 2

递归函数通常是处理某些数据结构(例如树和F#列表)的最自然的方式.如果编译器想要将我自然,直观的代码转换为一个尴尬的while循环,出于性能原因那么好,但为什么我要自己写呢？

此外,Brian 对相关问题的回答与此相关.高阶函数通常可以替换代码中的循环和递归函数.

Answer 3

F#执行尾部优化的事实只是一个实现细节,它允许您以相同的效率(并且不用担心堆栈溢出)使用尾递归作为while循环.但只是 - 一个实现细节 - 在表面上你的算法仍然是递归的并且以这种方式构造,对于许多算法来说,这是表示它的最合乎逻辑的,功能性的方式.

这同样适用于F#中的一些列表处理内部 - 内部变异用于更有效地实现列表操作,但这一事实对程序员来说是隐藏的.

它归结为语言如何允许您描述和实现您的算法,而不是使用什么技术来实现它.