使用F#循环vs递归

Question

这里的示例代码解决了项目Euler问题:

从数字1开始并沿顺时针方向向右移动,形成5乘5螺旋,如下所示:

 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.

以相同方式形成的1001乘1001螺旋中对角线上的数字总和是多少？

但我的问题是函数式编程风格而不是如何得到答案(我已经拥有它).我试图通过避免我的解决方案中的命令性循环来教自己一些关于函数式编程的知识,因此提出了以下递归函数来解决问题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#强制您将变量显式声明为可变并且不包含+ =运算符这一事实:

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,但这最终比我的递归版本更加混乱.

Answer 1

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

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

你不使用increment_index任何东西,所以你可以只繁殖increment和current四并获得相同的结果:

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

那么你的必要解决方案就变成:

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 

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

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然后可以重复使用):

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)

注意:我不确定这实际上是否实现了你想要的.它只是对命令式解决方案的简化,然后使用递归函数重写它...