2

我现在使用了许多递归函数，但仍然难以理解这样的函数究竟是如何工作的（我熟悉第二行（即| n==0 = 1）但对最后一行（即）不太熟悉| n>0 = fac (n-1) * n）。

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

4 回答 4

8

递归算法与数学归纳法密切相关。也许研究其中一个会帮助你更好地理解另一个。

使用递归时需要牢记两个关键原则：

  • 基本情况
  • 感应步骤

归纳步骤通常是最困难的部分，因为它假定它所依赖的所有内容都已正确计算。实现这种信念的飞跃可能很困难（至少我花了一段时间才掌握它），但这只是因为我们对我们的功能有先决条件；必须指定这些先决条件（在这种情况下，即n非负整数），以便归纳步骤和基本情况始终为真。

基本情况有时也很困难：比如说，你知道阶乘N!是N * (N-1)!，但你究竟如何处理阶梯上的第一步？（在这种情况下，很容易定义0! := 1。这个明确的定义为您提供了一种终止归纳步骤的递归应用的方法。）

您可以在此函数中看到您的类型规范和保护模式提供了保证 Inductive Step 可以反复使用直到达到 Base Case 的先决条件n == 0。如果不能满足先决条件，归纳步骤的递归应用将无法达到基本案例，并且您的计算将永远不会终止。（好吧，它会在内存不足时使用。:)

一个复杂的因素，特别是对于函数式编程语言，是非常强烈的希望重写所有“简单”递归函数，就像你在这里一样，使用尾调用或尾递归的变体。

因为这个函数调用自己，然后对结果执行另一个操作，你可以构建一个这样的调用链：

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 中的尾递归

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

（嵌套只是为了展示；运行时系统实际上不会将执行的详细信息存储在堆栈上。）

无论 的值如何，它都在常量内存中运行，n因此这种优化可以将“不可能”算法转换为“可能”算法。您将看到这种技术在函数式编程中广泛使用，就像您char *在 C 编程或yieldRuby 编程中经常看到的一样。

于 2011-05-14T02:25:32.643 回答
4

当你写| condition = expression它时，它会引入一个guard。从上到下依次尝试守卫，直到找到真正的条件，相应的表达式是您的函数的结果。

这意味着如果n为零，则结果为1，否则如果n > 0结果为fac (n-1) * n。如果n为负数，则会出现不完整的模式匹配错误。

一旦确定了要使用的表达式，只需代入递归调用即可查看发生了什么。

fac 4
(fac 3) * 4
((fac 2) * 3) * 4
(((fac 1) * 2) * 3) * 4
((((fac 0) * 1) * 2) * 3) * 4
(((1 * 1) * 2) * 3) * 4
((1 * 2) * 3) * 4
(2 * 3) * 4
6 * 4
24
于 2011-05-14T02:13:33.960 回答
2

特别是对于更复杂的递归案例，挽救心理健康的诀窍不是遵循递归调用，而是假设它们“做正确的事”。例如，在您的 fac 示例中，您想要计算fac n. 想象一下，你已经有了结果fac (n-1)。然后计算起来很简单fac n：只需将它乘以 n。但归纳法的神奇之处在于，这种推理确实有效（只要您提供适当的基本情况以终止递归）。因此，例如对于斐波那契数，只需查看基本情况是什么，并假设您能够计算所有小于 n 的数字的函数：

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

看？你要计算fib n。如果您知道fib (n-1)和 ，这很容易fib (n-2)。但是您可以简单地假设您能够计算它们，并且递归的“更深层次”做了“正确的事情”。所以只要使用它们，它就会起作用。

请注意，有更好的方法来编写此函数，因为目前许多值经常重新计算。

顺便说一句：“最好”的写作fac方式是fac n = product [1..n].

于 2011-05-14T10:54:38.450 回答
1

你怎么了？也许守卫（的|）是令人困惑的事情。

您可以将守卫松散地视为 if 链或 switch 语句（差异只有一个可以运行，并且它直接评估结果。不执行一系列任务，当然也没有副作用。只是评估到一个值）

平移命令式的伪代码......

Fac n:
   if n == 0: return 1
   if n > 0: return n * (result of calling fac w/ n decreased by one)

其他海报的调用树看起来可能会有所帮助。帮自己一个忙，真正地走过它

于 2011-05-14T02:14:49.200 回答