首页 > 代码库 > 10.1.1.1 使用累加器参数

10.1.1.1 使用累加器参数

10.1.1.1 使用累加器参数

 

我们考虑一下,如何把 sumList 函数改成尾递归,即,只在参数值是 cons cell (非空的列表)的分支上,执行一次递归调用。我们的经验法则表明,不应该很难,但目前,它做的事情,不止是返回递归调用的结果:把头中的值与总和相加。

要把这个函数变成尾递归函数,可以使用提供累加器参数(accumulator argument)的方法。计算结果时,不再从右到左跳转(在前面的图中,回到原来的函数调用),把计算出的结果,作为在递归调用前运行操作的一部分。我们需要为函数添加另一个参数,提供当前的结果。清单 10.2 显示了这种方法。

 

清单 10.2 尾递归的 sumList 函数 (F# Interactive)

> let rnd = new System.Random()

   let test1 = List.init 10000(fun _ -> rnd.Next(-50, 51))    | [1]

   let test2 = List.init 100000(fun _ -> rnd.Next(-50, 51);;   |

val rnd : Random

val test1 : int list = [1; -14; -35; 34;-1; -39; ...]

val test2 : int list = [29; -44; -1; 25;-33; 36; ...]

 

> let sumList(lst) =

     let recsumListUtil(lst, total) =  [2]

     match lst with

     | [] -> total    [3]

     |hd::tl –>

       letntotal = hd + total    [4]

      sumListUtil(tl, ntotal)  <-- 进行递归调用

     sumListUtil(lst,0);;    <-- 用 total = 0 调用辅助函数

val sumList : int list –> int

 

> sumList(test1);;    |

val it : int = –2120    | 调用两次

                  | 计算结果

> sumList(test2);;    |

val it : int = 8736     |

 

清单 10.2 首先生成两个包含随机数的列表[1]。我们使用 List.init 函数,把列表要求的长度作为第一个参数值,调用所提供的函数,计算指定索引处元素的值。在计算过程中,我们没有使用索引,因此,用 “_” 忽略它。究其原因,我们需要更好的测试输入,如果计算 1 到10 万之间所有数字的和,会得到不正确的结果,因为,结果超过 32 位整数。我们产生随机数在 –50 到 50 之间,因此,在原则上,计算的和应非常接近于零。

清单中最重要的部分是 sumList 函数。当使用累加器参数时,还需要再写一个函数,有一个额外的参数。我们通常不希望调用者看到这个参数,因此,把它作为局部函数[2];累加器参数(在示例中为total)保存当前的结果。当到达列表的结束时,结果也就有了,因此,只要返回它就行了[3];否则,把头中的值和结果相加,把累加器设置成新的值[4],然后,执行递归调用。图 10.4 显示了新的计算模型如何工作的。无论是调用工具函数,还是调用内部递归函数,都立即返回结果,因此,可以使用尾调用运行。

图 10.4 运行尾递归函数 sumList。第一次调用工具函数,跟踪当前的结果,使用累加器参数(total),计算前面所有元素的和。

 

sumList 例子并不难,演示了使用累加器的原理。为函数添加另一个参数,在进行递归调用之前,用来计算临时结果。打算把函数改成尾递归,要找到在递归调用后使用的当前信息,想办法把它传递给递归调用。

当我们讨论列表处理时,将看到更有技巧的示例,现在,要先讨论另外一个重要的优化方法:记忆化(memoization,缓存函数返回值)。

 

10.1.1.1 使用累加器参数