时间戳

首页 > 解决方案 > 这两个定义是相同的还是不同的

recursion - 这两个定义是相同的还是不同的

问题描述

查看以下定义：

let rec extractOdds list = ​
  match list with ​
  | [] -> []​
  | x::xs -> ​
      if x%2=0 then extractOdds xs else x::extractOdds xs​

和

let rec extractOdds list = ​
  match list with ​
  | [] -> []​
  | x::xs -> ​
      let rest = extractOdds xs​
      if x%2=0 then rest else x::rest​

我想知道两者是否相同。因为，第一个定义直接使用递归调用。而第二个创建了一个 let 绑定extractOdds xs并在if表达式中使用它。

如果两者的实施方式相同或不同，请指导我。

标签： recursionf#

解决方案

两者之间有一个非常小的差异，在实践中没有影响：

  • 第一个版本x%2=0在评估之前评估条件extractOdds xs
  • 第二个版本extractOdds xs在评估条件之前调用x%2=0

该顺序将保留在编译后的代码中（对于第一个版本可能会更长一些），因此两个版本略有不同，但这在任何情况下都无法观察到 - 这两个调用没有副作用并且extractOdds xs不管x%2=0istrue还是false. _

如果您也使用let绑定重写第一个版本，这可能会更明显：

let rec extractOdds list = ​
  match list with ​
  | [] -> []​
  | x::xs -> ​
      if x%2=0 then 
        let rest = extractOdds xs 
        rest 
      else 
        let rest = extractOdds xs​
        x::rest

现在您可以清楚地看到，条件的顺序和 let 绑定是唯一的区别：

let rec extractOdds list = ​
  match list with ​
  | [] -> []​
  | x::xs -> ​
      let rest = extractOdds xs​
      if x%2=0 then 
        rest 
      else 
        x::rest

编辑：可以使用“累加器”参数编写尾递归版本。这样，您以错误的顺序收集元素，因此您需要在返回结果列表之前反转结果列表：

let rec extractOdds acc list = ​
  match list with ​
  | [] -> List.rev acc
  | x::xs -> ​
      extractOdds (if x%2=0 then acc else x::acc) xs​

推荐阅读