递归函数中的栈实现

Question

我正在尝试使用深度优先搜索实现递归回溯功能，但我遇到了一个问题，我需要知道我之前在矩阵中的位置。

想法是这样的：我有一个矩阵作为二维数组，这是我的函数：

标记当前点，如果该点是我要查找的点，我将矩阵中的点设置为解决方案的一部分，并将之前标记的所有点设置为解决方案的一部分。否则我将函数调用到有效的相邻点。

问题是第三种情况：如果没有有效的相邻点，那么我需要将该点标记为错误并将函数调用到我之前的位置。为此，我认为我需要一个堆栈来跟踪我之前的移动，但我很难弄清楚如何在 f# 中执行此操作。

let rec  solve (x,y) =

         mark (x,y)

         if (x,y) = pointimlookingfor then
           for x in 0.. array width-1 do
               for y in 0..array height-1 do
                   if Myarray.[x,y]=markedpoint then
                      Myarray.[x,y]<-partofsolution

         else if (List.isEmpty(adjacentslist) then
              Myarray.[x,y]<-wrong point
              solve (the previous visited point)

         else 
              for (adjacentpoint) in adjacentslist do
                   solve(adjacentpoint)

有什么想法吗？

Answer 1

在大多数函数式语言中，默认列表类型是不可变链表，由于其构造，您可以将其用作简单堆栈。

cons 入栈，head 出栈。这样，我们就可以编写一个简单的堆栈模块了。

module Stack =
    let empty = []
    let push item stack = item::stack
    let pop = function
    | [] -> failwith "No items in stack"
    | x::xs -> xs
    let peek stack = stack |> List.tryHead

所以，

Stack.empty |> Stack.push 1 |> Stack.push 2 |> Stack.pop |> Stack.pop = Stack.empty //true

在实际操作中，最简单的方法是在随身携带的累加器上使用模式匹配，而不是像上面那样显式使用函数 recurse/fold。

例如，让我们为堆栈重新创建一个经典用例 - balancing parenthesis。每次遇到开大括号就入栈，遇到闭大括号就出栈，看是否和上次压入的匹配，如果不匹配，就是不平衡。

let rec isBalanced stack = function
| '(' | '{' | '[' as opened -> opened::stack //push into stack
| ')' | '}' | ']' as closed -> 
    match stack with
    | opened::rest as all -> //pop from stack
        match opened, closed with
        | '(', ')' 
        | '{', '}' 
        | '[', ']' -> rest
        | _ -> failwith "Mismatched braces"
    | [] -> failwith "Closing before open"
| _ -> stack

"abc() { [ 1; 2; 3] }" |> Seq.fold (isBalanced) []

有更简洁的写法，但这说明了如何模拟具有不可变结构的经典堆栈。

在您的情况下，您可以将 (x,y) 元组压入堆栈，并通过对其进行解构让算法回溯：(x,y)::tail.

递归函数中的栈实现

Stack implementation in recursive function

recursion

stack

f#

backtracking

depth-first-search