试图让我了解Haskell的递归？

Question

我现在已经使用了很多递归函数,但仍然无法理解这样一个函数是如何工作的(我熟悉第二行(即| n==0 = 1),但我对最后一行(即| n>0 = fac (n-1) * n)不太熟悉).

fac :: Int -> Int
fac n
    | n==0 = 1
    | n>0  = fac (n-1) * n

Answer 1

递归算法与数学归纳密切相关.也许学习一个会帮助你更好地理解另一个.

使用递归时,您需要记住两个关键原则:

归纳步骤通常是最难的部分,因为它假设它所依赖的一切都已经正确计算出来.实现信仰的这种飞跃可能很困难(至少我需要一段时间才能掌握它),但这只是因为我们的功能有先决条件 ; n必须指定那些前提条件(在这种情况下,这是一个非负整数),以便归纳步骤和基本情况始终为真.

基础案例有时也很困难:比如,你知道阶乘N!是N * (N-1)!,但你究竟如何处理阶梯的第一步？(在这种情况下,很容易定义0! := 1.这个显式定义为您提供了一种终止归纳步骤的递归应用的方法.)

您可以看到此函数中的类型规范和保护模式提供了保证Inductive Step可以一次又一次地使用直到它到达基本情况的前提条件n == 0.如果无法满足前提条件,则归纳步骤的递归应用将无法到达基本情况,并且您的计算将永远不会终止.(好吧,它会耗尽内存.:)

一个复杂的因素,特别是函数式编程语言,非常强烈地希望重新编写所有"简单"的递归函数,就像你在这里一样,使用Tail Calls或Tail Recursion的变体.

因为此函数调用自身,然后对结果执行另一个操作,您可以构建如下所示的调用链:

fac 3        3 * fac 2
  fac 2      2 * fac 1
    fac 1    1 * fac 0
      fac 0  1
    fac 1    1
  fac 2      2
fac 3        6

深度调用栈会占用内存; 但是一个编译器注意到函数在进行递归调用后没有改变任何状态可以优化掉递归调用.这些类型的函数通常传递累加器参数.另一个堆栈器有一个非常好的例子:Haskell中的Tail Recursion

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

这个非常复杂的变化:)意味着前一个调用链变成了这个:

fac 3 1       fac 2 3
  fac 2 3     fac 1 6
    fac 1 6   6

(嵌套只用于show;运行时系统实际上不会在堆栈上存储执行的细节.)

无论值如何,它都在恒定的内存中运行n,因此这种优化可以将"不可能"的算法转换为"可能的"算法.你会看到这种技术在函数式编程中被广泛使用,就像你char *经常在C编程中看到的那样,或者yield经常在Ruby编程中看到这种技术.