F# 编程/递归
| F# : 递归和递归函数 |
递归函数是指调用自身的函数。有趣的是，与许多其他语言不同，F# 中的函数默认情况下不是递归的。程序员需要使用rec关键字显式地将函数标记为递归。
let rec someFunction = ...
非负整数 n 的阶乘，用 n! 表示，是所有小于或等于 n 的正整数的乘积。例如，6! = 6 * 5 * 4 * 3 * 2 * 1 = 720。
在数学中，阶乘定义如下
自然地，我们会用手计算阶乘，如下所示
fact(6) =
= 6 * fact(6 - 1)
= 6 * 5 * fact(5 - 1)
= 6 * 5 * 4 * fact(4 - 1)
= 6 * 5 * 4 * 3 * fact(3 - 1)
= 6 * 5 * 4 * 3 * 2 * fact(2 - 1)
= 6 * 5 * 4 * 3 * 2 * 1 * fact(1 - 1)
= 6 * 5 * 4 * 3 * 2 * 1 * 1
= 720
在 F# 中，阶乘函数可以简明地编写如下
let rec fact x =
if x < 1 then 1
else x * fact (x - 1)
但请注意，此函数按原样返回所有负数的 1，但阶乘对于负数是未定义的。这意味着在实际的生产程序中，您必须要么设计程序的其余部分，使其永远不会使用负数调用阶乘，要么捕获负输入并抛出异常。异常将在后面的章节中讨论。
这是一个完整的程序
open System
let rec fact x =
if x < 1 then 1
else x * fact (x - 1)
(* // can also be written using pattern matching syntax:
let rec fact = function
| n when n < 1 -> 1
| n -> n * fact (n - 1) *)
Console.WriteLine(fact 6)
最大公约数或 GCD 函数计算能整除另外两个整数的最大整数。例如，能整除 259 和 111 的最大数是 37，记为 GCD(259, 111) = 37。
欧几里得发现了一种非常简单的递归算法来计算两个数的 GCD
为了用手计算，我们会写
gcd(259, 111) = gcd(111, 259% 111)
= gcd(111, 37)
= gcd(37, 111% 37)
= gcd(37, 0)
= 37
在 F# 中，我们可以使用%（模数）运算符来计算两个数的余数，因此我们自然可以将 F# 中的 GCD 函数定义如下
open System
let rec gcd x y =
if y = 0 then x
else gcd y (x % y)
Console.WriteLine(gcd 259 111) // prints 37
假设我们有一个函数A，它在某个时刻调用函数B。当B执行完毕时，CPU 必须从中断的地方继续执行A。为了“记住”返回的位置，函数A将一个返回地址作为额外的参数传递给堆栈上的B；B在执行完毕后跳转到返回地址。这意味着调用函数，即使是没有任何参数的函数，也会消耗堆栈空间，并且递归函数很容易消耗堆栈上的所有可用内存。
一个尾递归函数是递归的一种特殊情况，其中方法中执行的最后一条指令是递归调用。F# 和许多其他函数式语言可以优化尾递归函数；由于递归调用后没有执行额外的操作，因此函数不需要记住它来自哪里，因此没有理由在堆栈上分配额外的内存。
F# 通过告诉 CLR 在执行目标函数之前放弃当前堆栈帧来优化尾递归函数。因此，尾递归函数可以无限递归，而不会消耗堆栈空间。
这是一个非尾递归函数
> let rec count n =
if n = 1000000 then
printfn "done"
else
if n % 1000 = 0 then
printfn "n: %i" n
count (n + 1) (* recursive call *)
() (* <-- This function is not tail recursive
because it performs extra work (by
returning unit) after
the recursive call is invoked. *);;
val count : int -> unit
> count 0;;
n: 0
n: 1000
n: 2000
n: 3000
...
n: 58000
n: 59000
Session termination detected. Press Enter to restart.
Process is terminated due to StackOverflowException.
让我们看看如果我们使函数正确地尾递归会发生什么
> let rec count n =
if n = 1000000 then
printfn "done"
else
if n % 1000 = 0 then
printfn "n: %i" n
count (n + 1) (* recursive call *);;
val count : int -> unit
> count 0;;
n: 0
n: 1000
n: 2000
n: 3000
n: 4000
...
n: 995000
n: 996000
n: 997000
n: 998000
n: 999000
done
如果没有对n = 1000000进行检查，函数将无限运行。确保所有递归函数都有一个基本情况以确保它们最终终止非常重要。
假设为了娱乐，我们想根据更基本的加法函数来实现乘法函数。例如，我们知道6 * 4与6 + 6 + 6 + 6相同，或者更一般地，我们可以递归地定义乘法为M(a, b) = a + M(a, b - 1), b > 1。在 F# 中，我们将这样编写这个函数
let rec slowMultiply a b =
if b > 1 then
a + slowMultiply a (b - 1)
else
a
可能并不立即显而易见，但此函数不是尾递归的。如果我们将函数改写如下，可能更加明显
let rec slowMultiply a b =
if b > 1 then
let intermediate = slowMultiply a (b - 1) (* recursion *)
let result = a + intermediate (* <-- additional operations *)
result
else a
它不是尾递归的原因是在递归调用slowMultiply之后，必须将递归的结果加到a。请记住，尾递归需要最后一步是递归。
由于slowMultiply函数不是尾递归的，因此对于导致非常深层递归的输入，它会抛出StackOverFlowException
> let rec slowMultiply a b =
if b > 1 then
a + slowMultiply a (b - 1)
else
a;;
val slowMultiply : int -> int -> int
> slowMultiply 3 9;;
val it : int = 27
> slowMultiply 2 14;;
val it : int = 28
> slowMultiply 1 100000;;
Process is terminated due to StackOverflowException.
Session termination detected. Press Enter to restart.
可以使用累加参数将大多数递归函数重写为尾递归形式
> let slowMultiply a b =
let rec loop acc counter =
if counter > 1 then
loop (acc + a) (counter - 1) (* tail recursive *)
else
acc
loop a b;;
val slowMultiply : int -> int -> int
> slowMultiply 3 9;;
val it : int = 27
> slowMultiply 2 14;;
val it : int = 28
> slowMultiply 1 100000;;
val it : int = 100000
内部循环中的累加器参数在每次递归迭代中保存函数的状态。
解决方案.
以下函数计算斐波那契数列中的第n个数字
let rec fib = function
| n when n=0I -> 0I
| n when n=1I -> 1I
| n -> fib(n - 1I) + fib(n - 2I)
- 注意: 上述函数的类型为
val fib : bigint -> bigint。之前我们一直在使用int或System.Int32类型来表示数字，但这种类型最大值为2,147,483,647。类型bigint用于任意大小整数，例如具有数十亿位数的整数。bigint的最大值仅受用户机器上可用内存的限制，但对于大多数实际的计算目的，我们可以说此类型是无界的。
上述函数既不是尾递归，也不是特别有效，其计算复杂度为O(2n)。此函数的尾递归形式的计算复杂度为O(n)。重写上述函数，使其成为尾递归。
您可以使用以下内容验证函数的正确性
fib(0I) = 0 fib(1I) = 1 fib(2I) = 1 fib(3I) = 2 fib(4I) = 3 fib(5I) = 5 fib(10I) = 55 fib(100I) = 354224848179261915075