recursion - 使用 F# 进行循环与递归

Question

这里的示例代码解决了一个项目欧拉问题:

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

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

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

但我的问题是函数式编程风格的问题，而不是如何获得答案(我已经有了答案)。我试图通过避免解决方案中的命令式循环来自学一些关于函数式编程的知识，因此想出了以下递归函数来解决问题 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)

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