用F#循环vs递归 [英] Looping vs recursion with F#

问题描述

此处的示例代码解决了项目Euler问题:

The example code here solves a project Euler problem:

从数字1开始，然后沿顺时针方向向右移动 形成5 x 5螺旋的方向如下:

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

 21 22 23 24 25 
 20  7  8  9 10  
 19  6  1  2 11    
 18  5  4  3 12 
 17 16 15 14 13

可以验证对角线上的数字之和为 101.

It can be verified that the sum of the numbers on the diagonals is 101.

1001 x 1001中对角线上的数字之和是多少 螺旋以同样的方式形成吗?

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

但是我的问题是函数编程风格的问题，而不是如何获得答案的(我已经知道了).我试图通过避免解决方案中的命令式循环来教自己一些有关函数式编程的知识，因此想出了以下递归函数来解决问题28:

but my question is a matter of functional programming style rather than about how to get the answer (I already have it). I am trying to teach myself a bit about functional programming by avoiding imperative loops in my solutions, and so came up with the following recursive function to solve problem 28:

let answer = 
    let dimensions = 1001
    let max_number = dimensions * dimensions

    let rec loop total increment increment_count current =
        if current > max_number then total
        else
            let new_inc, new_inc_count =
                if increment_count = 4 then increment + 2, 0
                else increment, increment_count + 1
            loop (total + current) new_inc new_inc_count (current + increment)            
    loop 0 2 1 1

但是，在我看来，我的功能有点混乱.即使考虑到F#强制您将变量显式声明为可变变量且不包含+ =运算符的事实，以下命令式版本也更加简短明了:

However, it seems to me my function is a bit of a mess. The following imperative version is shorter and clearer, even after taking into account the fact that F# forces you to explicitly declare variables as mutable and doesn't include a += operator:

let answer = 
    let dimensions = 1001
    let mutable total = 1
    let mutable increment = 2
    let mutable current = 1

    for spiral_layer_index in {1..(dimensions- 1) / 2} do
        for increment_index in {1..4} do
            current <- current + increment
            total <- total + current 
        increment <- increment + 2
    total

不管数学能力更高的人都可以通过分析解决问题，是否有更好的方法来实现这种功能?我还尝试过使用Seq.unfold创建一个值序列，然后将结果序列管道传输到Seq.sum中，但这最终比我的递归版本还要混乱.

Disregarding the fact that people with more maths ability have solved the problem analytically, is there a better way to do this in a functional style? I also tried using Seq.unfold to create a sequence of values and then piping the resulting sequence into Seq.sum, but this ended up being even messier than my recursive version.

推荐答案

由于您没有描述要解决的问题，因此此答案仅基于您发布的F#代码.我同意功能版本有点混乱，但我认为它可能会更清晰.我不太了解命令式解决方案中的嵌套for循环:

Since you didn't describe the problem you're trying to solve, this answer is based only on the F# code you posted. I agree that the functional version is a bit messy, but I believe it could be clearer. I don't really understand the nested for loop in your imperative solution:

for increment_index in {1..4} do 
  current <- current + increment 
  total <- total + current  

您没有使用increment_index进行任何操作，因此您可以将increment和current乘以4并得到相同的结果:

You're not using the increment_index for anything, so you could just multiply increment and current by four and get the same result:

total <- total + 4*current + 10*increment
current <- current + 4*increment

那么您的当务之急就是:

Then your imperative solution becomes:

let mutable total = 0 
let mutable increment = 2 
let mutable current = 1 

for spiral_layer_index in {1..(dimensions- 1) / 2} do 
  total <- total + 4*current + 10*increment
  current <- current + 4*increment
  increment <- increment + 2 
total 

如果将其重写为递归函数，它将变为:

If you rewrite this to a recursive function, it becomes just:

let rec loop index (total, current, increment) = 
  if index > (dimensions - 1) / 2 then total 
  else loop (index + 1) ( total + 4*current + 10*increment,
                          current + 4*increment, increment + 2 )
let total = loop 1 (0, 2, 1)

也可以使用Seq.fold这样写同一件事(这甚至更功能化"，因为在函数式编程中，您仅使用递归来实现基本功能，例如fold，然后可以重复使用) ):

The same thing could be also written using Seq.fold like this (this is even more "functional", because in functional programming, you use recursion only to implement basic functions, like fold that can then be re-used):

let total, _, _=
  {1 .. (dimensions - 1) / 2} |> Seq.fold (fun (total, current, increment) _ ->
    (total + 4*current + 10*increment, current + 4 * increment, increment + 2)) (0, 1, 2)

注意:我不确定这是否真正实现了您想要的.这只是简化命令式解决方案，然后使用递归函数将其重写...

NOTE: I'm not sure if this actually implements what you want. It is just a simplification of your imperative solution and then rewrite of that using a recursive function...

这篇关于用F#循环vs递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！