虽然在F＃中使用Tail Recursion，但在什么时候使用？

5 回答

• 5

  最好的答案是'既不' . :)

  有一些丑陋与while循环和尾递归相关联 .

  虽然循环需要可变性和效果，虽然我没有反对使用它们，特别是当封装在本地函数的上下文中时，当你开始将效果仅仅引入循环时，你有时会感到混乱/丑化你的程序 .

  尾递归通常具有需要额外累加器参数或延续传递样式的缺点 . 这使程序与额外的样板杂乱，以按摩功能的启动条件 .

  最好的答案是既不使用while循环也不使用递归 . 高阶函数和lambdas是你的救星，特别是 Map 和折叠 . 当你可以将它们封装在可重用的库中然后只是简单地和声明性地陈述你的计算的本质时，为什么要使用凌乱的控制结构来进行循环呢？

  如果您养成经常调用map / fold而不是使用循环/递归的习惯，以及提供折叠函数以及您引入的任何新的树结构数据类型，您将走得更远 . :)

  对于那些有兴趣了解F＃折叠的人，为什么不查看我在这个主题的系列文章中的帖子？#2640334_ three blog？

  回复于 2024-04-26T16:09:19+08:00
• 29

  按照首选项和一般编程风格，我将编写如下代码：

  Map/fold if its available

  let x = [1 .. 10] |> List.map ((*) 2)
  

  它只是方便易用 .

  Non-tail recursive function

  > let rec map f = function
      | x::xs -> f x::map f xs
      | [] -> [];;
  
  val map : ('a -> 'b) -> 'a list -> 'b list
  
  > [1 .. 10] |> map ((*) 2);;
  val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
  

  大多数算法最容易阅读和表达，没有尾递归 . 当你不需要过度递归时，这种方法特别有效，使其适用于许多排序算法和 balancer 数据结构上的大多数操作 .

  请记住，log2（1,000,000,000,000,000）〜= 50，因此没有尾递归的log（n）操作根本不可怕 .

  Tail-recursive with accumulator

  > let rev l =
      let rec loop acc = function
          | [] -> acc
          | x::xs -> loop (x::acc) xs
      loop [] l
  
  let map f l =
      let rec loop acc = function
          | [] -> rev acc
          | x::xs -> loop (f x::acc) xs
      loop [] l;;
  
  val rev : 'a list -> 'a list
  val map : ('a -> 'b) -> 'a list -> 'b list
  
  > [1 .. 10] |> map ((*) 2);;
  val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
  

  它很有用，但是代码很笨拙，算法的优雅也略显模糊 . 上面的例子读起来并不算太糟糕，但是一旦你进入树状数据结构，它真的开始成为一场噩梦 .

  Tail-recursive with continuation passing

  > let rec map cont f = function
      | [] -> cont []
      | x::xs -> map (fun l -> cont <| f x::l) f xs;;
  
  val map : ('a list -> 'b) -> ('c -> 'a) -> 'c list -> 'b
  
  > [1 .. 10] |> map id ((*) 2);;
  val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
  

  每当我看到这样的代码时，我都会对自己说"now that's a neat trick!" . 以可读性为代价，它保持了非递归函数的形状，并且发现tail-recursive inserts into binary trees非常有趣 .

  它可能是我的monad-phobia在这里讲的，或者也许我对Lisp的调用/ cc缺乏熟悉，但我认为CSP实际上简化算法的那些场合很少见 . 评论中欢迎反例 .

  While loops / for loops

  在我看来，除了序列理解之外，我从来没有在我的F＃代码中使用while或for循环 . 在任何情况下...

  > let map f l =
      let l' = ref l
      let acc = ref []
      while not <| List.isEmpty !l' do
          acc := (!l' |> List.hd |> f)::!acc
          l' := !l' |> List.tl
      !acc |> List.rev;;
  
  val map : ('a -> 'b) -> 'a list -> 'b list
  
  > [1 .. 10] |> map ((*) 2);;
  val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
  

  它实际上是对命令式编程的模仿 . 您可以通过声明 let mutable l' = l 来保持一点理智，但任何非平凡的功能都需要使用 ref .

  回复于 2024-04-26T16:09:19+08:00
• 21

  许多问题都具有递归性质，但长时间强制思考常常会阻止我们看到这一点 .

  一般来说，我会尽可能在函数式语言中使用函数技术 - 循环从不起作用，因为它们完全依赖于副作用 . 因此，在处理命令式代码或算法时，使用循环是足够的，但在功能上下文中，它们并不被认为是非常好的 .

  功能技术不仅意味着递归，还使用适当的高阶函数 .

  因此，当对一个列表进行求和时，for循环和递归函数都没有 fold 是具有可理解代码而不重新发明轮子的解决方案 .

  回复于 2024-04-26T16:09:19+08:00
• 2

  老实说，你可以通过循环解决的任何问题已经是一个自然递归的问题，因为你可以将两者都翻译成（通常有条件的）跳到最后 .

  我相信在几乎所有必须编写显式循环的情况下，你应该坚持使用尾调用 . 它更加通用：

  • while循环将您限制为一个循环体，而尾调用可以允许您在"loop"运行时在多个不同状态之间切换 .

  • while循环将您限制为一个条件以检查终止，尾递归您可以使用任意复杂的匹配表达式等待将控制流分流到其他位置 .

  • 您的尾调用都返回有用的值，并可能产生有用的类型错误 . while循环不会返回任何内容，并依赖于副作用来完成其工作 .

  • 虽然循环不是第一类，而尾部调用的函数（或其中的循环）是 . 可以检查本地范围内的递归绑定的类型 .

  • 尾递归函数可以很容易地分解为使用尾调用以所需顺序相互调用的部分 . 这可能会使事情更容易阅读，如果您发现想要在循环中开始，这将有所帮助 . 这不是一个while循环 .

  总而言之，F＃中的循环只是值得，如果你真的要在函数体内处理可变状态，重复做同样的事情直到满足某个条件 . 如果循环通常有用或非常复杂，您可能希望将其分解为其他顶级绑定 . 如果数据类型本身是不可变的（许多.NET值类型都是），那么无论如何都可能从使用对它们的可变引用中获得很少 .

  我会说你应该只采用while循环来获取适合工作的时间循环，并且相对较短 . 在许多命令式编程语言中，while循环经常被扭曲成不自然的角色，比如在case语句中反复驱动东西 . 避免这些事情，看看你是否可以使用尾调用，或者更好的是更高阶函数，以达到同样的目的 .

  回复于 2024-04-26T16:09:19+08:00
• 5

  对于那些不是自然递归的问题..无论如何只是在while循环中转换它

  你自己回答了这个 . 将递归用于递归问题，并循环用于本质上不起作用的事物 . 总是想：哪种感觉更自然，哪种更具可读性 .

  回复于 2024-04-26T16:09:19+08:00